Finding and enumerating Hamilton cycles in 4-regular graphs

We show that each 4-regular n-vertex graph contains at most O(18n/5)≤O(1.783n) Hamilton cycles, which improves a previous bound by Sharir and Welzl. From the other side we exhibit a family of graphs with 48n/8≥1.622n Hamilton cycles per graph.Moreover, we present an algorithm which finds the minimum weight Hamilton cycle of a given 4-regular graph in time , improving on Eppstein’s previous bound. This algorithm can be modified to compute the number of Hamilton cycles in the same time bound and to enumerate all Hamilton cycles in time with denoting the number of Hamilton cycles of the given graph G. So our upper bound of O(1.783n) for the number of Hamilton cycles serves also as a time bound for enumeration.