On two cycles of consecutive even lengths

DOI10.1002/JGT.23074arXiv2210.03959OpenAlexW4391170001WikidataQ129556900 ScholiaQ129556900MaRDI QIDQ6413311

Binlong Li, Tianying Xie, Jun Gao, Jie Ma

Publication date: 8 October 2022

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_5$, 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"ete. The quantitative bound is tight and also provides the optimal extremal number for cycles of length two modulo four.

Full work available at URL: https://doi.org/10.1002/jgt.23074

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Vertex degrees (05C07)

This page was built for publication: On two cycles of consecutive even lengths