报告题目: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
联系人:冯星
欢迎广大师生前往并提前下载客户端,以免错过报告!