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