The Maximum Number of Paths of Length Four in a Planar Graph


Abstract in English

Let $f(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. The order of magnitude of $f(n,P_k)$, where $P_k$ is a path of length $k$, is $n^{{lfloor{frac{k}{2}}rfloor}+1}$. In this paper we determine the asymptotic value of $f(n,P_4)$ and give conjectures for longer paths.

Download