CHORDS OF LONGEST CYCLES IN CUBIC GRAPHS

We describe a general sufficient condition for a Hamiltonian graph to contain another Hamiltonian cycle. We apply it to prove that every lon gest cycle in a S-connected cubic graph has a chord. We also verify sp ecial cases of an old conjecture of Sheehan on Hamiltonian cycles in 4 -regular graphs and a recent conjecture on a second Hamiltonian cycle by Triesch, Nolles, and Vygen. (C) 1997 Academic Press.