The maximum number of P_l copies in P_k-free graphs

Main Article Content

Ervin Győri Nika Salia Casey Tompkins Oscar Zamora


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.

Article Details

How to Cite
Győri, E., Salia, N., Tompkins, C., & Zamora, O. (2019). The maximum number of P_l copies in P_k-free graphs. Acta Mathematica Universitatis Comenianae, 88(3), 773-778. Retrieved from