2138cn太阳集团古天乐|(首页欢迎您)

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

2138cn太阳集团古天乐学术报告—宁博副教授

【来源: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项和科技部重点研发计划。



报告时间:2021101710:00开始

报告方式线上报告(腾讯会议)

ID106 241 175

联系人:冯星

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