报告题目：Stability in Bondy's theorem on paths and cycles

摘   要：In this talk, 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 the idea behind 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 $\min\{2\delta(G)+2,n\}$. This problem 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.

宁博副教授简介

宁博，理学博士，南洋理工大学访问学者。曾在天津大学任教，现任南开大学副教授。研究兴趣主要是结构图论、极值图论和谱图理论，在《Combinatorica》、《J. Combin. Theory Ser. B 》、《Combin. Probab. Comput.》、《SIAM J. Discrete Math.》、《 J. Graph Theory》等国际期刊发表论文40余篇，主持国家自然科学基金2项，参与国家自然科学基金2项和科技部重点研发计划。

报告时间：2021年10月17日上午10:00开始

报告方式：线上报告（腾讯会议）

会 议 ID：106 241 175

联系人：冯星

欢迎广大师生前往并提前下载客户端，以免错过报告！