1 results
THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 98 / Issue 1 / August 2018
- Published online by Cambridge University Press:
- 03 May 2018, pp. 18-26
- Print publication:
- August 2018
-
- Article
-
- You have access
- Export citation
-
By Smith’s theorem, if a cubic graph has a Hamiltonian cycle, then it has a second Hamiltonian cycle. Thomason [‘Hamilton cycles and uniquely edge-colourable graphs’, Ann. Discrete Math.3 (1978), 259–268] gave a simple algorithm to find the second cycle. Thomassen [private communication] observed that if there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in a cubic cyclically 4-edge connected graph
$G$, then there exists a polynomially bounded algorithm for finding a second Hamiltonian cycle in any cubic graph 
$G$. In this paper we present a class of cyclically 4-edge connected cubic bipartite graphs 
$G_{i}$ with 
$16(i+1)$ vertices such that Thomason’s algorithm takes 
$12(2^{i}-1)+3$ steps to find a second Hamiltonian cycle in 
$G_{i}$.
