On the number of longest and almost longest cycles in cubic graphs

Gek Ling Chia, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    2 Downloads (Pure)


    We consider the questions: How many longest cycles must a cubic graph have, and how many may it have? For each k >= 2 there are infinitely many p such that there is a cubic graph with p vertices and precisely one longest cycle of length p-k. On the other hand, if G is a graph with p vertices, all of which have odd degree, and its longest cycle has length p-1, then it has a second (but not necessarily a third) longest cycle. We presents results and conjectures on the maximum number of cycles in cubic multigraphs of girth 2, 3, 4, respectively. For cubic cyclically 5-edge-connected graphs we have no conjecture but, we believe that the generalized Petersen graphs P(n, k) are relevant. We enumerate the hamiltonian and almost hamiltonian cycles in each P(n, 2). Curiously, there are many of one type if and only there are few of the other. If n is odd, then P(2n, 2) is a covering graph of P(n, 2). (For example, the dodecahedron graph is a covering graph of the Petersen graph). Another curiosity is that one of these has many (respectively few) hamiltonian cycles if and only if the other has few (respectively many) almost hamiltonian cycles.
    Original languageEnglish
    JournalArs Combinatoria
    Pages (from-to)307-320
    Publication statusPublished - 2012


    • Hamiltonian cycles


    Dive into the research topics of 'On the number of longest and almost longest cycles in cubic graphs'. Together they form a unique fingerprint.

    Cite this