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

Publication: Research - peer-reviewJournal article – Annual report year: 2012

View graph of relations

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
StatePublished - 2012


  • Hamiltonian cycles
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 10181111