Geodesic
The maximum number of $P_\ell$ copies in $P_k$-free graphs
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1

Voir la notice de l'article provenant de la source Episciences

Generalizing Tur\'an'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\H{o}s and Gallai. 
@article{DMTCS_2019_21_1_a13,
     author = {Gy\H{o}ri, Ervin and Salia, Nika and Tompkins, Casey and Zamora, Oscar},
     title = {The maximum number of $P_\ell$ copies in $P_k$-free graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-14},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-14/}
}
TY  - JOUR
AU  - Győri, Ervin
AU  - Salia, Nika
AU  - Tompkins, Casey
AU  - Zamora, Oscar
TI  - The maximum number of $P_\ell$ copies in $P_k$-free graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-14/
DO  - 10.23638/DMTCS-21-1-14
LA  - en
ID  - DMTCS_2019_21_1_a13
ER  - 
%0 Journal Article
%A Győri, Ervin
%A Salia, Nika
%A Tompkins, Casey
%A Zamora, Oscar
%T The maximum number of $P_\ell$ copies in $P_k$-free graphs
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-14/
%R 10.23638/DMTCS-21-1-14
%G en
%F DMTCS_2019_21_1_a13
Győri, Ervin; Salia, Nika; Tompkins, Casey; Zamora, Oscar. The maximum number of $P_\ell$ copies in $P_k$-free graphs. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi: 10.23638/DMTCS-21-1-14

Cité par Sources :