On the minimum number of Hamiltonian cycles in regular graphs

DOI10.1080/10586458.2017.1306813MaRDI QIDQ4646702zbMATH OpenOpenAlexFDO

Authors Micheal Haythorpe

Publication date 14 January 2019

Published in Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

minimalHamiltonian cyclesregular graphsconstruction

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(17)

• 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
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Regular graphs with few longest cycles
• scientific article; zbMATH DE number 4061286 (Why is no real title available?)
• Graphs with few 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
• The number of Hamiltonian decompositions of regular graphs
• Estimation of the number of Hamiltonian cycles in regular graphs of special type
• Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles
• \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• From one to many rainbow Hamiltonian cycles
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Generating 4-regular Hamiltonian plane graphs

Describes a project that uses

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)