On two cycles of consecutive even lengths

2022/10/08 by Jun Gao, Gao, Jun, Binlong Li +5 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2210.03959

openalex publication_date 2022/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Bondy and Vince showed that every graph with minimum degree at least three contains two cycles of lengths differing by one or two.We prove the following average degree counterpart that every n-vertex graph G with at least \frac52(n-1) edges, unless 4|(n-1) and every block of G is a clique K₅, contains two cycles of consecutive even lengths. Our proof is mainly based on structural analysis, and a crucial step which may be of independent interest shows that the same conclusion holds for every 3-connected graph with at least 6 vertices. This solves a special case of a conjecture of Verstraëte. The quantitative bound is tight and also provides the optimal extremal number for cycles of length two modulo four.

Cited by

• Cycle lengths in graphs of given minimum degree
• Cycles of consecutive lengths in 3-connected graphs

Related

• A note on two cycles of consecutive even lengths in graphs
• On a conjecture of Bondy and Vince
• Arithmetic Progressions of Cycle Lengths in Graphs
• A unified proof of conjectures on cycle lengths in graphs
• A conjecture of Verstraëte on vertex-disjoint cycles