The maximum number of P_l copies in P_k-free graphs

Abstract

Generalizing Tur\'an's classical extremal problem, Alon and Shikhelman investigated the problem of maximizing the number of copies of $T$ in an $H$-free graph, for a pair of graphs $T$ and $H$.  Whereas Alon and Shikhelman were primarily interested in determining the order of magnitude for some classes of graphs $H$, we focus on the case when $T$ and $H$ are paths, where we find asymptotic and exact results in some cases. We also consider other structures like stars and the set of cycles of length at least $k$, where we  derive asymptotically sharp estimates.  Our results generalize well-known extremal theorems of Erd\H{o}s and Gallai.