2021/04/20 by Carol T. Zamfirescu, Zamfirescu, Carol T.
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Finite Group Theory Research
paper · pdf · doi:10.48550/arxiv.2104.10020
Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant c such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly c hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput, and that it holds for 4-regular graphs of connectivity 2 with the constant 144 < c, which we believe to be minimal among all hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every non-negative integer k there is a 5-regular graph on 26 + 6k vertices with 2k+10 ⋅ 3k+3 hamiltonian cycles. We prove that for every d ≥ 3 there is an infinite family of hamiltonian 3-connected graphs with minimum degree d, with a bounded number of hamiltonian cycles. It is shown that if a 3-regular graph G has a unique longest cycle C, at least two components of G - E(C) have an odd number of vertices on C, and that there exist 3-regular graphs with exactly two such components.