»ã±¨Ö÷Ì⣺ƽÃæÈý½ÇÆÊ·ÖͼµÄHamiltonianȦÊý£¨Number of Hamiltonian cycles in planar triangulations£©

»ã±¨ÈË£ºÓôÐÇÐÇ ½ÌÊÚ £¨×ôÖÎÑÇÀí¹¤Ñ§ÔºÊýѧϵ£©

»ã±¨¹¦·ò£º2020Äê9ÔÂ29ÈÕ£¨Öܶþ£© 9:00

²Î»á·½Ê½£ºÌÚѶ»áÒé

£¨https://meeting.tencent.com/s/wO06wi7HPusV£©

»áÒéID£º974 973 657

£»

»áÒéÃÜÂ룺200929

Ö÷°ì²¿ÃÅ£ºÐ±¦GGÔ˳ïÓëÓÅ»¯Ê¢¿ª³¢ÊÔÊÒ-¹ú¼Ê¿ÆÑкÏ×÷ƽ̨¡¢ÉϺ£ÊÐÔ˳ïѧ»á¡¢Ð±¦GGÀíѧԺÊýѧϵ

»ã±¨ÌáÒª£º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.

Ó­½ÓÀÏʦ¡¢Ñ§Éú²ÎÓ룡