zbMATH — the first resource for mathematics

On the minimum number of Hamiltonian cycles in regular graphs. (English) Zbl 1403.05082
Summary: A graph construction that produces a \(k\)-regular graph on \(n\) vertices for any choice of \(k\geq 3\) and \(n=m(k+1)\) for integer \(m\geq 2\) is described. The number of Hamiltonians cycles in such graphs can be explicitly determined as a function of \(n\) and \(k\), and empirical evidence is provided that suggests that this function gives a tight upper bound on the minimum number of Hamiltonian cycles in \(k\)-regular graphs on \(n\) vertices for \(k\) \(\geq 5\) and \(n\geq k+3\). An additional graph construction for 4-regular graphs is described for which the number of Hamiltonian cycles is superior to the above function in the case when \(k=4\) and \(n\geq 11\).

05C45 Eulerian and Hamiltonian graphs
05C30 Enumeration in graph theory
Full Text: DOI
[1] Biggs, [Biggs 93] N. L., Algebraic Graph Theory, (1993), Cambridge, UK: Cambridge University Press
[2] Bogard, [Bogard and Doyle 86] K. P.; Doyle, P. G., Nonsexist Solution of the Menage Problem, Amer. Math. Monthly, 93, 7, 514-519, (1986)
[3] Chalaturnyk, [Chalaturnyk 08] A., A Fast Algorithm for Finding Hamilton Cycles, (2008), University of Manitoba
[4] Eppstein, [Eppstein 07] D., The Traveling Salesman Problem for Cucubic Graphs, J. Graph Algorithms Appl., 11, 1, 61-81, (2007) · Zbl 1161.68662
[5] Garey, [Garey et al. 76] M. R.; Johnson, D. S.; Tarjan, R. E., The Planar Hamiltonian Circuit Problem is NP-complete, SIAM J. Comput., 5, 4, 704-714, (1976) · Zbl 0346.05110
[6] Gebauer, [Gebauer 08] H., On the number of Hamilton cycles in bounded degree graphs, Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, 241-248, (2008)
[7] Haxell, [Haxell and Seamone 07] P.; Seamone, B.; Verstraete, J., Independent Dominating Sets and Hamiltonian Cycles, J. Graph Theory, 54, 3, 233-244, (2007) · Zbl 1112.05077
[8] Meringer, [Meringer 99] M., Fast Generation of Regular Graphs and Constructions of Cages, J. Graph Theorey, 30, 137-146 · Zbl 0918.05062
[9] Robinson, [Robinson and Whittaker 67] G.; Whittaker (Eds.), E. T., Stirling’s Approximation to the Factorial, The Calculus of Obervations: A Treatise on Numerical Mathematics, 138-140, (1967), New York: Dover, New York
[10] Sheehan, [Sheehan 75] J., The multiplicity of Hamiltonian circuits in a graph, Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 477-480, (1975)
[11] Singmaster, [Singmaster 75] D., Hamiltonian Circuits on the n-dimensional Octohedron, J. Comb. Theory, Ser. B, 19, 1, 1-4, (1975) · Zbl 0281.05108
[12] Tutte, [Tutte 46] W. T., On Hamiltonian Circuits, J. London Math. Soc., 21, 98-101, (1946) · Zbl 0061.41306
[13] Watkins, [Watkins 69] M. E., A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, J. Combinatorial Theory, 6, 152-164, (1969) · Zbl 0175.50303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.