Length of cycles in generalized Petersen graphs

Abstract

There have been extensive researchs on cycles in regular graphs, particularly 3-connected cubic graphs. Generalized Petersen graphs, denoted by GP(n,k),are highly symmetric 3-connected cubic graphs, which have attracted great attention. The Hamiltonicity of GP(n,k) has been studied for a long time and thoroughlysettled. Inspired by Bondy’s meta-conjecture that almost every nontrivial condition for Hamiltonicity also implies pancyclicity, we seek for more cycle structures in thisclass of graphs, by figuring out the possible lengths of cycles in them.It turns out that generalized Petersen graphs, though not generally pancyclic, miss only very few possible length of cycles. For k ∈ {2,3}, we completely determineall possible cycle lengths in GP(n,k). We also obtain some results for GP(n,k) where k is odd. In particular, when k is odd, and n is even and sufficiently large,GP(n,k) is bipartite and weakly even pancyclic.