A Second Hamiltonian Cycle

11:00 AM-12:00 PM

*Room: Liberty B*

*Chair: Edward Scheinerman, Johns Hopkins University*

The problem of finding a Hamiltonian cycle in a graph is NP-complete.
We do not know the complexity of the following problem. Given a graph
with a Hamiltonian cycle *C*, does *G* contain a
Hamiltonian cycle distinct from *C*? A classical result of
Cedric Smith says that the answer is affirmative if *G* is
cubic. More generally, Andrew Thomason proved that the answer is
affirmative if all vertices of *G* have odd degree. John Sheehan
conjectured in 1975 that the answer is affirmative also if *G*
is 4-regular. In this presentation, the speaker will present a
general sufficient condition for a second Hamiltonian cycle. Combined
with Lovasz' local lemma, this implies that every *r*-regular
Hamiltonian graph has a second Hamiltonian cycle except possibly for
finitely many values of *r*. (Sheehan's conjecture would imply
that there are no exceptions). Moreover, in a bipartite Hamiltonian
graph, the number of Hamiltonian cycles increases (at least)
exponentially as a function of the minimum degree. And in the cubic
case, that number increases (at least) exponentially as a function of
the girth.

**Carsten Thomassen**

*Technical University of Denmark*

*Lyngby, Denmark*

*MMD, 10/13/98*