The number of induced paths in outerplanar graphs

Abstract

Let $P_k$ denote the path with $k$ vertices, and ${\mathrm{ex}}_{\mathcal{O}\mathcal{P}}(n,H^{\mathrm{ind}},\varnothing )$ 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{O}\mathcal{P}}(n,P_3^{\mathrm{ind}},\varnothing )$ for all $n$, and give an asymptotic value of ${\mathrm{ex}}_{\mathcal{O}\mathcal{P}}(n,P_4^{\mathrm{ind}},\varnothing )$. For general $k$, Matolcsi and Nagy proved that ${\lim }_{k\to \infty }{\left({\mathrm{ex}}_{\mathcal{O}\mathcal{P}}(n,P_{k+1},\varnothing )\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{O}\mathcal{P}}(n,P_{k+1}^{\mathrm{ind}},\varnothing )\right)}^{1/k}=\frac{\sqrt{5}+1}{2}\approx 1.618$.