Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
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.
DOI :
10.37236/619
Classification :
05C38, 05C30, 05C35, 05C45, 05C85
Mots-clés : enumeration, maximum number, Hamilton cycles, partial Hamilton cycles, algorithm
Mots-clés : enumeration, maximum number, Hamilton cycles, partial Hamilton cycles, algorithm
@article{10_37236_619,
author = {Heidi Gebauer},
title = {Enumerating all {Hamilton} cycles and bounding the number of {Hamilton} cycles in 3-regular graphs},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/619},
zbl = {1219.05077},
url = {http://geodesic.mathdoc.fr/articles/10.37236/619/}
}
Heidi Gebauer. Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/619
Cité par Sources :