The Complexity of Finding a Second Hamiltonian Cycle in Cubic Graphs

摘要

Smith's theorem states that in a cubic graph the number of Hamiltonian cycles containing a given edge is even. Thomason's proof of this theorem yields an algorithm that given one Hamiltonian cycle in such a graph, computes another one. We prove an exponential lower bound on the number of steps of Thomason's algorithm.