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

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

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

参会方法：腾讯聚会

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

聚会ID：974 973 657；；

聚会密码：200929

主理部分：8188cc威尼斯运筹与优化开放实验室-国际科研相助平台、上海市运筹学会、8188cc威尼斯理学院数学系

报告摘要：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.

接待西席、学生加入！