On the number of hamiltonian cycles in a maximal planar graph
S. L. Hakimi, Edward F. Schmeichel, Carsten Thomassen · Journal of Graph Theory · 1979
Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4‐connected maximal planar graph on p vertices contains at least p/(log2 p) Hamiltonian cycles.