
doi: 10.37236/619
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.
partial Hamilton cycles, Extremal problems in graph theory, Eulerian and Hamiltonian graphs, algorithm, Graph algorithms (graph-theoretic aspects), maximum number, Enumeration in graph theory, Paths and cycles, Hamilton cycles, enumeration
partial Hamilton cycles, Extremal problems in graph theory, Eulerian and Hamiltonian graphs, algorithm, Graph algorithms (graph-theoretic aspects), maximum number, Enumeration in graph theory, Paths and cycles, Hamilton cycles, enumeration
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
