Stability in Bondy's theorem on paths and cycles

arXiv2207.13650MaRDI QIDQ6406275FDOQ6406275

Authors: Bo Ning, Long-Tu Yuan 

Publication date: 27 July 2022

Abstract: In this paper, we study the stability result of a well-known theorem of Bondy. We prove that for any 2-connected non-hamiltonian graph, if every vertex except for at most one vertex has degree at least $k$, then it contains a cycle of length at least $2k+2$ except for some special families of graphs. Our results imply several previous classical theorems including a deep and old result by Voss. We point out our result on stability in Bondy's theorem can directly imply a positive solution to the following problem: Is there a polynomial time algorithm to decide whether a 2-connected graph $G$ on $n$ vertices has a cycle of length at least $min2delta(G)+2,n$. This problem cite[Question~1]{FGSS-Arxiv} originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin et al., although a stronger problem was solved by them by completely different methods. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory.

This page was built for publication: Stability in Bondy's theorem on paths and cycles

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