Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T19:08:36.012Z Has data issue: false hasContentIssue false

THE COMPLEXITY OF THOMASON’S ALGORITHM FOR FINDING A SECOND HAMILTONIAN CYCLE

Part of:Graph theory

Published online by Cambridge University Press:  03 May 2018

LIANG ZHONG*
Affiliation:
Center for Discrete Mathematics, Fuzhou University, Fujian-Fuzhou, China email zhongliangll@126.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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}$ .

Information

Type
Research Article
Copyright
© 2018 Australian Mathematical Publishing Association Inc.