## Project Details

### Description

In 1996 we have developed a general method for finding a second

hamiltonian cycle in a hamiltonian graph. The method

has been used to attack the conjecture made by Thomassen

in 1976 that every longest cycle in a 3-connected graph

has a chord. The conjecture has now been verified for cubic

graphs. Furthermore, it has been proved in a joint work

with R.E.L. Aldred, New Zealand, that the number of cycles

in a cubic, 3-connected graph grows superpolynomial, a

conjecture made in 1986 by Barefoot, Clark and Entringer.

In 1997 we have combined the sufficient condition for a second hamiltonian cycle in terms of independent dominating sets with Lovasz' Local Lemma to prove that every hamiltonian r-regular graph has a second hamiltonian cycle if r is at least 300. This is a step towards the 1975 conjecture of John Sheehan that every such graph has a second hamiltonian graph provided r is at least 4. In 1997 we also proved the conjecture made by Bermond, Fouquet, Habib and Peroche in 1984 that every cubic graph has a 2-edge-coloring such that each monochromatic component is a path of length at most 5. The number 5 cannot be replaced by 4.

hamiltonian cycle in a hamiltonian graph. The method

has been used to attack the conjecture made by Thomassen

in 1976 that every longest cycle in a 3-connected graph

has a chord. The conjecture has now been verified for cubic

graphs. Furthermore, it has been proved in a joint work

with R.E.L. Aldred, New Zealand, that the number of cycles

in a cubic, 3-connected graph grows superpolynomial, a

conjecture made in 1986 by Barefoot, Clark and Entringer.

In 1997 we have combined the sufficient condition for a second hamiltonian cycle in terms of independent dominating sets with Lovasz' Local Lemma to prove that every hamiltonian r-regular graph has a second hamiltonian cycle if r is at least 300. This is a step towards the 1975 conjecture of John Sheehan that every such graph has a second hamiltonian graph provided r is at least 4. In 1997 we also proved the conjecture made by Bermond, Fouquet, Habib and Peroche in 1984 that every cubic graph has a 2-edge-coloring such that each monochromatic component is a path of length at most 5. The number 5 cannot be replaced by 4.

Status | Finished |
---|---|

Effective start/end date | 01/01/1996 → 31/12/1998 |