On two cycles of consecutive even lengths

DOI10.1002/JGT.23074MaRDI QIDQ6413311zbMATH OpenOpenAlexWikidataFDO

Authors Jun Gao, Binlong Li, Jie Ma, T. Xie

Publication date 8 October 2022

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Distribution of cycle lengths in graphs
• Cycles of even lengths modulo k
• scientific article; zbMATH DE number 6692113
• Cycles with consecutive odd lengths
• Cycle lengths and minimum degree of graphs

Cited in

(5)

• On graphs without cycles of length 0 modulo 4
• A note on two cycles of consecutive even lengths in graphs
• A strengthening on consecutive odd cycles in graphs of given minimum degree
• Maximum number of cliques in \(\{C_{k_1}, C_{k_2}, C_{k_3}, \cdots \}\)-free graphs with \(6 = k_1 < k_2 < \cdots\) and \(k_{i+1} - k_i \leq 5\)
• Cycle lengths in graphs of given minimum degree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413311)