论文标题
邦迪定理的稳定性在路径和周期上
Stability in Bondy's theorem on paths and cycles
论文作者
论文摘要
在本文中，我们研究了著名的邦迪定理的稳定性结果。我们证明，对于任何2个连接的非汉密尔顿图，如果每个顶点除了最多一个顶点，则每个顶点至少具有至少$ k $，则它包含一个长度至少$ 2K+2 $的周期，除了一些特殊的图形家庭。我们的结果暗示了以前的几种古典定理，包括Voss的深层和旧结果。我们指出我们对邦迪定理稳定性的结果可以直接暗示着以下问题的积极解决方案（以稍强的形式）：是否存在多项式时间算法来决定是否有2个连接的图形$ g $上的$ n $ vertices上的$ n $ vertices的长度至少长度为$ \ min \ min \ min \ min \ min \ {2Δ（g）+2g）+2，N \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \} $。这个问题最初激发了Fomin，Golovach，Sagunov和Simonov的Dirac定理算法方面的最新研究，尽管他们通过完全不同的方法解决了更强大的问题。我们的定理还可以帮助我们确定奇数顶点上车轮的所有极端图。我们还讨论了我们的结果与一些以前的问题与频谱图理论中的定理之间的关系和广义的Turán问题。
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 (in a slight stronger form) 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 $\min\{2δ(G)+2,n\}$. This problem originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin, Golovach, Sagunov and Simonov, although a stronger problem was solved by them by completely different methods. Our theorem can also help us to determine all extremal graphs for wheels on odd number of vertices. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized Turán problem.
