On a conjecture of Bondy and Vince

DOI10.1016/J.JCTB.2019.07.005MaRDI QIDQ2284740zbMATH OpenOpenAlexFDO

Authors Jun Gao, Jie Ma

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05701

zbMATH Keywords

Bondy-Vince conjectureconsecutive cyclescycle lengthgraphs of minimum degree three

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Twenty years ago Bondy and Vince conjectured that for any nonnegative integer $k$, except finitely many counterexamples, every graph with $k$ vertices of degree less than three contains two cycles whose lengths differ by one or two. The case $kleq2$ was proved by Bondy and Vince, which resolved an earlier conjecture of ErdH{o}s et. al.. In this paper we confirm this conjecture for all $k$.

Recommendations

• On a conjecture of Bondy
• scientific article; zbMATH DE number 68367
• On Vandiver's conjecture
• On Vizing's conjecture
• scientific article; zbMATH DE number 140092
• On a conjecture of Vukman
• On Varea's conjecture
• scientific article; zbMATH DE number 1214986
• scientific article; zbMATH DE number 1080117
• On a conjecture of Vorst

Cites work

• A unified proof of conjectures on cycle lengths in graphs
• Cycle lengths and minimum degree of graphs
• Cycle lengths in sparse graphs
• Distribution of cycle lengths in graphs
• Extremal problems for cycles in graphs
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 861419 (Why is no real title available?)
• Non-separating induced cycles in graphs
• On arithmetic progressions of cycle lengths in graphs
• Some old and new problems in various branches of combinatorics

Cited in

(6)

• On a conjecture of Bondy
• scientific article; zbMATH DE number 3914357 (Why is no real title available?)
• scientific article; zbMATH DE number 68367 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 2230942 (Why is no real title available?)
• Minimum degree conditions for the existence of a sequence of cycles whose lengths differ by one or two

This page was built for publication: On a conjecture of Bondy and Vince

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