平面三角剖分图的Hamiltonian圈数



活动地点:腾讯会议

活动时间:2020-09-29 09:00:00

报告主题:平面三角剖分图的Hamiltonian圈数(Number of Hamiltonian cycles in planar triangulations)

报告人:郁星星 教授 (佐治亚理工学院数学系)

报告时间:2020年9月29日(周二) 9:00

参会方式:腾讯会议

(https://meeting.tencent.com/s/wO06wi7HPusV)

会议ID:974 973 657;

会议密码:200929

主办部门:上海大学运筹与优化开放实验室-国际科研合作平台、上海市运筹学会、上海大学理学院数学系

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

 

欢迎教师、学生参加!

  • 快速导航
  • 国际交流

  • 上海大学主页

  • 上海大学官方微博

  • 上海大学公众号

  • 上海大学信息门户
上海大学新闻网
信息公开
招聘信息
文明校园创建
海外学习与实习
校园美景.VI展示
校友会
教育发展基金会
校医院
网络安全小贴士
校长信箱

版权所有 ? 上海大学   沪ICP备09014157   地址:上海市宝山区上大路99号   邮编:200444   电话总机:021-96928188   校内电话查询
互联网违法和不良信息举报   举报电话   举报邮箱   沪公网安备31009102000049号
技术支持:上海大学信息化工作办公室   联系我们