Cycles in Graphs

    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.
    StatusFinished
    Effective start/end date01/01/199631/12/1998