Stability results on Bondy’s theorem on paths and cycles

：宁博（南开大学）
：2024-12-23 14:30
：海韵园行政楼C610

报告人：宁博（南开大学）

时  间：2024年12月23日14:30

地  点：海韵园行政楼C610

内容摘要:

In this talk, we discuss about the stability result of a well-known theorem of Bondy. We shall show 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. The last but not least, we shall discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized Turán problem. In particular, we shall present some work proved by other authors which uses our results as some new tool.

个人简介：

宁博，南开大学计算机学院副教授、博士生导师、南开大学百名青年学科带头人（A类）。主要研究结构图论和极值组合，在Combinatorica和JCTB等图论领域期刊发表SCI论文50余篇。主持国家自然科学基金项目4项，参与重点研发项目2项。入选国家高层次青年人才，曾在第九届世界华人数学家大会作45分钟特邀报告，并获第八届中国运筹学会青年科技奖。

 

联系人：金贤安