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

DOI10.1016/J.DISC.2017.12.018zbMATH Open1383.05172arXiv1704.02866OpenAlexW2964120982MaRDI QIDQ1709520FDOQ1709520

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)

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.

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

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

zbMATH Keywords

pathscyclesTurán problem

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• On Hamilton's ideals
• On maximal paths and circuits of graphs
• The history of degenerate (bipartite) extremal graph problems
• Path Ramsey numbers in multicolorings
• Maximal circuits of graphs. I
• On maximal circuits in directed graphs
• Stability in the Erdős-Gallai theorems on cycles and paths
• Long paths and large cycles in finite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (17)

• 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
• Extremal graphs for the odd prism
• Maximizing the number of cliques in graphs with given matching number
• Stability in the Erdős-Gallai theorems on cycles and paths
• How connectivity affects the extremal number of trees
• Stability results on the circumference of a graph
• 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
• Circumference, minimum degree and clique number
• Erdős-Gallai stability theorem for linear forests
• Revisit of Erdős-Gallai's theorem on the circumference of a graph
• Extensions of the Erdős-Gallai theorem and Luo's theorem

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)