The complexity of finding a second hamiltonian cycle in cubic graphs

Authors
Krawczyk, A
Citation
A. Krawczyk, The complexity of finding a second hamiltonian cycle in cubic graphs, J COMPUT SY, 58(3), 1999, pp. 641-647
Citations number
8
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
00220000 → ACNP
Volume
58
Issue
3
Year of publication
1999
Pages
641 - 647
Database
ISI
SICI code
0022-0000(199906)58:3<641:TCOFAS>2.0.ZU;2-Z
Abstract
Smith's theorem states that in a cubic graph the number of Hamiltonian cycl es 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 an other one. We prove an exponential lower bound on the number of steps of Th omason's algorithm. (C) 1999 Academic Press.