Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs (Q547792)

Summary: We describe an algorithm which enumerates all Hamilton cycles of a given 3- regular \(n\)-vertex graph in time \(O(1.276^n)\), improving on Eppstein's previous bound. The resulting new upper bound of \(O(1.276^n)\) for the maximum number of Hamilton cycles in 3-regular \(n\)-vertex graphs gets close to the best known lower bound of \(\Omega (1.259^n)\). Our method differs from Eppstein's in that he considers in each step a new graph and modifies it, while we fix (at the very beginning) one Hamilton cycle \(C\) and then proceed around \(C\), successively producing partial Hamilton cycles.