The maximum number of P_\ell copies in P_k-free graphs

MaRDI QIDQ5226834zbMATH OpenFDO

Authors Nika Salia, Casey Tompkins, Oscar Zamora, Ervin Győri

Publication date 1 August 2019

Full work available at URL https://arxiv.org/abs/1803.03240, https://dmtcs.episciences.org/5622/pdf

zbMATH Keywords

cyclepathextremalgeneralized Turán

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: 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 ErdH{o}s and Gallai.

Recommendations

• Counting copies of a fixed subgraph in \(F\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• The Turán number of disjoint copies of paths
• Many H-copies in graphs with a forbidden tree

Cited in

(23)

• The maximum number of stars in a graph without linear forest
• The maximum number of \(P_\ell\) copies in \(P_k\)-free graphs
• Tree densities in sparse graph classes
• Many \(T\) copies in \(H\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Unified approach to the generalized Turán problem and supersaturation
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Generalized regular Turán numbers
• Supersaturation for subgraph counts
• Random polynomial graphs for random Turán problems
• Many H-copies in graphs with a forbidden tree
• On graphs that contain exactly \(k\) copies of a subgraph, and a related problem in search theory
• Generalized Turán problems for even cycles
• Subgraph densities in a surface
• The maximum number of paths of length three in a planar graph
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• Exact results on generalized Erdős-Gallai problems
• The constructor-blocker game
• Further results on the generalized Turán number of spanning linear forests
• Some exact results for generalized Turán problems
• The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths
• Some results on \(k\)-Turán-good graphs
• Ordering \(Q\)-indices of graphs: given size and circumference

This page was built for publication: The maximum number of $P_\ell$ copies in $P_k$-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226834)