NUMBER OF HAMILTONIAN CYCLES IN PLANAR TRIANGULATIONS

摘要

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. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar n-vertex triangulations G that do not have too many separating 4-cycles or have minimum degree 5. 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) = 5, then G has 2 Omega (n1/4) Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a "double wheel" structure, providing further evidence to the above conjecture.