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 - 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

SN - 0012-365X

VL - 341

SP - 1253

EP - 1263

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -