Stability in the Erdős-Gallai theorem on cycles and paths. II

DOI10.1016/J.DISC.2017.12.018MaRDI QIDQ1709520zbMATH OpenOpenAlexFDO

Authors Ruth Luo, Zoltán Füredi, Alexandr Kostochka, J. Verstraëte

Publication date 5 April 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02866

zbMATH Keywords

pathscyclesTurán problem

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: The ErdH{o}s--Gallai Theorem states that for $kgeq3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $frac12(k-1)(n-1)$ edges. A stronger version of the ErdH{o}s--Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e(G)leqmaxh(n,k,2),h(n,k,lfloorfrack-12floor)$, where $h(n,k,a):=k-achoose2+a(n-k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,lfloorfrack-12floor)$ edges. In this paper, we complete a stability theorem which strengthens Kopylov's result. In particular, we show that for $kgeq3$ odd and all $ngeqk$, every $n$-vertex $2$-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e(G)leqmaxh(n,k,3),h(n,k,frack-32)$. The upper bound for $e(G)$ here is tight.

Recommendations

• Stability in the Erdős-Gallai theorems on cycles and paths
• The maximum number of cliques in graphs without long cycles
• Stability results on the circumference of a graph
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Erdős-Gallai stability theorem for linear forests

Cites work

• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• scientific article; zbMATH DE number 3485842 (Why is no real title available?)
• scientific article; zbMATH DE number 3186566 (Why is no real title available?)
• Long paths and large cycles in finite graphs
• Maximal circuits of graphs. I
• On Hamilton's ideals
• On maximal circuits in directed graphs
• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Stability in the Erdős-Gallai theorems on cycles and paths
• The history of degenerate (bipartite) extremal graph problems

Cited in

(17)

• Extensions of the Erdős-Gallai theorem and Luo's theorem
• A stability result of the Pósa lemma
• Some sharp results on the generalized Turán numbers
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Stability of Woodall's theorem and spectral conditions for large cycles
• A note on the stability results of the number of cliques in graphs with given matching number
• Non-Hamiltonian graphs with large minimum degree
• Maximizing the number of cliques in graphs with given matching number
• Extremal graphs for the odd prism
• Stability in the Erdős-Gallai theorems on cycles and paths
• Stability results on the circumference of a graph
• How connectivity affects the extremal number of trees
• Linear three-uniform hypergraphs with no Berge path of given length
• Stability version of Dirac's theorem and its applications for generalized Turán problems
• Erdős-Gallai stability theorem for linear forests
• Circumference, minimum degree and clique number
• Revisit of Erdős-Gallai's theorem on the circumference of a graph

This page was built for publication: Stability in the Erdős-Gallai theorem on cycles and paths. II

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