The number of induced paths in outerplanar graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908960122994688 |
|---|---|
| author | Wang, Yichen Győri, Ervin Tompkins, Casey Zhao, Xiamiao |
| author_facet | Wang, Yichen Győri, Ervin Tompkins, Casey Zhao, Xiamiao |
| contents | Let $P_k$ denote the path with $k$ vertices, and $\mathrm{ex}_{\mathcal{OP}}(n,H^{\mathrm{ind}},\emptyset)$ be the maximum number of induced copies of $H$ in an $n$-vertex outerplanar graph. In this paper, we determine the exact value of $\mathrm{ex}_{\mathcal{OP}}(n,P_3^{\mathrm{ind}},\emptyset)$ for all $n$, and give an asymptotic value of $\mathrm{ex}_{\mathcal{OP}}(n,P_4^{\mathrm{ind}},\emptyset)$. For general $k$, Matolcsi and Nagy proved that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1},\emptyset)\right)^{1/k}} =4$. In the induced case, we prove that
\[
fib(k-1)\frac{{(n-2k+3)}^2}{4} \le \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset) \le fib(k+1) \binom{n}{2},
\]
where $fib(k)$ is the Fibonacci number. This implies that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset)\right)^{1/k}} = \frac{\sqrt{5}+1}{2}\approx 1.618$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11525 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The number of induced paths in outerplanar graphs Wang, Yichen Győri, Ervin Tompkins, Casey Zhao, Xiamiao Combinatorics 05C35 Let $P_k$ denote the path with $k$ vertices, and $\mathrm{ex}_{\mathcal{OP}}(n,H^{\mathrm{ind}},\emptyset)$ be the maximum number of induced copies of $H$ in an $n$-vertex outerplanar graph. In this paper, we determine the exact value of $\mathrm{ex}_{\mathcal{OP}}(n,P_3^{\mathrm{ind}},\emptyset)$ for all $n$, and give an asymptotic value of $\mathrm{ex}_{\mathcal{OP}}(n,P_4^{\mathrm{ind}},\emptyset)$. For general $k$, Matolcsi and Nagy proved that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1},\emptyset)\right)^{1/k}} =4$. In the induced case, we prove that \[ fib(k-1)\frac{{(n-2k+3)}^2}{4} \le \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset) \le fib(k+1) \binom{n}{2}, \] where $fib(k)$ is the Fibonacci number. This implies that $\lim_{k\to \infty} {\left( \mathrm{ex}_{\mathcal{OP}}(n, P_{k+1}^{\mathrm{ind}},\emptyset)\right)^{1/k}} = \frac{\sqrt{5}+1}{2}\approx 1.618$. |
| title | The number of induced paths in outerplanar graphs |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2604.11525 |