On the Number of Longest and Almost Longest Cycles in Cubic Graphs

Abstract

We consider the questions: How many longest cycles must a cubic graph have, and how many may it have? For each $k\ge 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 present 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 if 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.