学校首页|| Enghish
当前位置: 网站首页 > 通知公告 > 综合通知 > 正文


【来源:2138cn太阳集团古天乐学术报告—宁博副教授 | 发布日期:2021-10-16 】

报告题目: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项和科技部重点研发计划。



ID106 241 175