报告主题：平面三角剖分图的Hamiltonian圈数（Number of Hamiltonian cycles in planar triangulations）

报告人：郁星星 教授 （佐治亚理工学院数学系）

报告时间：2020年9月29日（周二） 9:00

参会方式：腾讯会议

（https://meeting.tencent.com/s/wO06wi7HPusV）

会议ID：974 973 657；

会议密码：200929

主办部门：8188威尼斯娱人城运筹与优化开放实验室-国际科研合作平台、上海市运筹学会、8188威尼斯娱人城理学院数学系

报告摘要：Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. We show that if $G$ has $O(n/{\log}_2 n)$ separating 4-cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G)\ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a “double wheel” structure, providing further evidence to the above conjecture. Joint work with Xiaonan Liu.

欢迎教师、学生参加！