For a planar graph $H$, let $operatorname{mathbf{N}}_{mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $operatorname{mathbf{N}}_{mathcal P}(n,P_7)sim{4over 27}n^4$, $operatorname{mathbf{N}}_{mathcal P}(n,C_6)sim(n/3)^3$, $operatorname{mathbf{N}}_{mathcal P}(n,C_8)sim(n/4)^4$ and $operatorname{mathbf{N}}_{mathcal P}(n,K_4{1})sim(n/6)^6$, where $K_4{1}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $operatorname{mathbf{N}}_{mathcal P}(n,P_{2m+1})$ and $operatorname{mathbf{N}}_{mathcal P}(n,C_{2m})$ for $mgeq 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $operatorname{mathbf{N}}_{mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs.
تحميل البحث