Ervin Győri ; Nika Salia ; Casey Tompkins ; Oscar Zamora
-
The maximum number of $P_\ell$ copies in $P_k$-free graphs
dmtcs:4958 -
Discrete Mathematics & Theoretical Computer Science,
July 13, 2019,
vol. 21 no. 1, ICGT 2018
-
https://doi.org/10.23638/DMTCS-21-1-14The maximum number of $P_\ell$ copies in $P_k$-free graphsArticleAuthors: Ervin Győri ; Nika Salia

; Casey Tompkins ; Oscar Zamora
NULL##0000-0003-3403-9686##NULL##NULL
Ervin Győri;Nika Salia;Casey Tompkins;Oscar Zamora
Generalizing Turán's classical extremal problem, Alon and Shikhelman investigated the problem of maximizing the number of $T$ copies 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 large classes of graphs $H$, we focus on the case when $T$ and $H$ are paths, where we find asymptotic and in some cases exact results. 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ős and Gallai.
Volume: vol. 21 no. 1, ICGT 2018
Published on: July 13, 2019
Accepted on: June 14, 2019
Submitted on: November 6, 2018
Keywords: Mathematics - Combinatorics