Hamiltonian cycles in 4-connected plane triangulations with few 4-separators (Q2005718)

This paper is a quantification of an old theorem of \textit{H. Whitney} [Ann. Math. (2) 32, 378--390 (1931; Zbl 0002.16101)] on the Hamiltonicity of triangulations. Witney proved that every triangulation which is 4-connected has a Hamilton cycle, that is, a cycle which traverses all vertices of the graph. In this paper, the author derives a result on the number of Hamilton cycles such a triangulation has, depending on the number of 4-separators. The author shows that there are constants \(c_1,c_2>0\) such that if \(G\) is a triangulation on \(n\) vertices with more than \(c_1 \log n\) 4-separators, that is, sets of size 4 whose removal disconnects the graph, then it has at least \(c_2 n^2 / \log^2 n\) Hamilton cycles. Higher connectivities are covered by a result of \textit{A. Alahmadi} et al. [J. Comb. Theory, Ser. B 140, 27--44 (2020; Zbl 1430.05018)] who showed that if \(G\) is a 5-connected triangulation, then it has \(2^{\Omega (n)}\) Hamilton cycles.