TY - JOUR

T1 - Stability in the Erdős–Gallai Theorem on cycles and paths, II

AU - Füredi, Zoltán

AU - Kostochka, Alexandr

AU - Luo, Ruth

AU - Verstraëte, Jacques

N1 - Funding Information:
The authors thank Zoltán Király and the referees for their helpful comments. The first author's research was supported in part by grant K116769 from the National Research, Development and Innovation Office NKFIH, by the Simons Foundation Collaboration Grant#317487, and by the European Research Council Advanced Investigators Grant267195. Research of the second author is supported in part by NSF grant DMS-1266016 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. Research of fourth author was supported by NSF Grant DMS-1101489.
Funding Information:
The authors thank Zoltán Király and the referees for their helpful comments. The first author’s research was supported in part by grant K116769 from the National Research, Development and Innovation Office NKFIH , by the Simons Foundation Collaboration Grant #317487 , and by the European Research Council Advanced Investigators Grant 267195 . Research of the second author is supported in part by NSF grant DMS-1266016 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research . Research of fourth author was supported by NSF Grant DMS-1101489 .
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/5

Y1 - 2018/5

N2 - The Erdős–Gallai Theorem states that for k≥3, any n-vertex graph with no cycle of length at least k has at most [Formula preseted](k−1)(n−1) edges. A stronger version of the Erdő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)≤max{h(n,k,2),h(n,k,⌊[Formula preseted]⌋)}, where h(n,k,a)≔[Formula preseted]+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,⌊[Formula preseted]⌋) edges. In this paper, we complete a stability theorem which strengthens Kopylov's result. In particular, we show that for k≥3 odd and all n≥k, 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)≤max{h(n,k,3),h(n,k,[Formula preseted])}. The upper bound for e(G) here is tight.

AB - The Erdős–Gallai Theorem states that for k≥3, any n-vertex graph with no cycle of length at least k has at most [Formula preseted](k−1)(n−1) edges. A stronger version of the Erdő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)≤max{h(n,k,2),h(n,k,⌊[Formula preseted]⌋)}, where h(n,k,a)≔[Formula preseted]+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,⌊[Formula preseted]⌋) edges. In this paper, we complete a stability theorem which strengthens Kopylov's result. In particular, we show that for k≥3 odd and all n≥k, 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)≤max{h(n,k,3),h(n,k,[Formula preseted])}. The upper bound for e(G) here is tight.

KW - Cycles

KW - Paths

KW - Turán problem

UR - http://www.scopus.com/inward/record.url?scp=85042255197&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85042255197&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2017.12.018

DO - 10.1016/j.disc.2017.12.018

M3 - Article

AN - SCOPUS:85042255197

VL - 341

SP - 1253

EP - 1263

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 5

ER -