On the minimum number of Hamiltonian cycles in regular graphs

DOI10.1080/10586458.2017.1306813zbMATH Open1403.05082arXiv1608.00713OpenAlexW2490772428MaRDI QIDQ4646702FDOQ4646702

Authors: Micheal Haythorpe 

Publication date: 14 January 2019

Published in: Experimental Mathematics (Search for Journal in Brave)

Abstract: A graph construction that produces a k-regular graph on n vertices for any choice of k >= 3 and n = m(k+1) for integer m >= 2 is described. The number of Hamiltonian 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 >= 5 and n >= 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 >= 11.

Full work available at URL: https://arxiv.org/abs/1608.00713

Recommendations

• Finding and enumerating Hamilton cycles in 4-regular graphs
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• On the number of Hamilton cycles in bounded degree graphs
• Hamiltonian cycles in regular graphs of moderate degree
• Hamilton cycles in regular 3-connected graphs

zbMATH Keywords

minimalHamiltonian cyclesregular graphsconstruction

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30)

Cites Work

• Fast generation of regular graphs and construction of cages
• The Traveling Salesman Problem for Cubic Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Independent dominating sets and hamiltonian cycles
• On Hamiltonian Circuits
• On the number of Hamilton cycles in bounded degree graphs
• Title not available (Why is that?)
• Non-Sexist Solution of the Menage Problem
• Hamiltonian circuits on the \(n\)-dimensional octahedron

Cited In (17)

• Regular graphs with few longest cycles
• From one to many rainbow Hamiltonian cycles
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs
• Few Hamiltonian cycles in graphs with one or two vertex degrees
• Complexity of the hamiltonian cycle in regular graph problem
• A lower bound on the number of hamiltonian cycles
• Graphs with few Hamiltonian cycles
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Generating 4-regular Hamiltonian plane graphs
• Title not available (Why is that?)
• Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
• The number of Hamiltonian decompositions of regular graphs
• Estimation of the number of Hamiltonian cycles in regular graphs of special type
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles

Uses Software

• GENREG

This page was built for publication: On the minimum number of Hamiltonian cycles in regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646702)