题目： Sufficient conditions for Hamilton cycles：old results and new viewpoints

报告人：宁博 (南开大学)

报告时间：2024年6月19日16:00-17:00

报告地点：理科楼A404

摘要： As an extension of Ore's condition on Hamilton cycles, Fan in 1984 proved that every 2-connected graph $G$ on $n\geq 3$ vertices is hamiltonian if $G$ satisfies Fan's condition, i.e., for every pair of vertices $x,y\in V(G)$, the fact $d(x,y)=2$ implies that $\max\{d(x),d(y)\}\geq \frac{n}{2}$. Moreover, Fan constructed a family of graphs called $F_{4r}$ which satisfies Fan’s condition but can imply its n-closure is not complete. In this talk, we first report a structural theorem for the new graph $G'$ which is obtained from a graph $G$ satisfying Fan's condition, by adding a series of new edges whose two end vertices are not adjacent and with degree sum at least $|G|$, and finally doing the Ryjacek's claw-free closure of the resulting graph. Our theorem shows that this new graph $G'$ (in the spirit of closure theory) looks like the structure of $F_{4r}$. We also show that the lower bound of the number of edges in a graph satisfying Fan's condition satisfies $\frac{n^2}{8}+Ώ(n)$, which is motivated by a classical theorem of Bondy. Moreover, this bound is best possible by considering the graph $F_{4r}$. With these two theorems in mind, we can see the graph $F_{4r}$ plays an important role in reasoning Fan's condition for Hamilton cycles.

报告人信息：宁博，南开大学计算机学院副教授、博士生导师、南开大学百名青年学科带头人。主要研究结构图论、极值图论和谱图论，在Combinatorica和JCTB等组合数学领域期刊发表学术论文50余篇。目前主持国家自然科学基金面上项目1项。获第八届中国运筹学会青年科技奖。

邀请人：陆玫