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

Abstract

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 on $k$ vertices, is $n^{\lfloor \frac{k-1}{2}\rfloor +1}$. In this paper we determine the asymptotic value of $f(n,P_5)$ and give conjectures for longer paths.

arXiv comment9 pages, 2 figures