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.
展开▼
机译：我们描述了一种算法，该算法在时间$ O（1.276 ^ {n}）$时枚举给定的3个正则$ n $-顶点图的所有汉密尔顿周期，并在Eppstein的先前边界上进行了改进。在3个正则$ n $-顶点图中汉密尔顿循环的最大数目的结果$ O（1.276 ^ {n}）$的新上限接近最著名的$ Omega（1.259 ^ {n }）$。我们的方法与Eppstein的方法不同之处在于，他在每一步中都会考虑一个新图并对其进行修改，而同时（在开始时）固定一个汉密尔顿循环$ C $，然后在$ C $附近进行操作，从而连续产生部分汉密尔顿循环。
展开▼
