Counting Hamiltonian cycles in planar triangulations

Hakimi, Schmeichel, and Thomassen (1979) [10] conjectured that every 4-connected planar triangulation G on n vertices has at least 2(n - 2)(n - 4) Hamiltonian cycles, with equality if and only if G is a double wheel. In this paper, we show that every 4-connected planar triangulation on n vertices has omega(n(2)) Hamiltonian cycles. Moreover, we show that if G is a 4-connected planar triangulation on n vertices and the distance between any two vertices of degree 4 in G is at least 3, then G has 2(omega(n1/4)) Hamiltonian cycles. (C)& nbsp;2022 Elsevier Inc. All rights reserved.