On the number of Hamiltonian cycles in the generalized Petersen graph

Abstract

The generalized Petersen graph $G(n,k)$ is a cubic graph with vertex set $V(G(n,k))=\{v_i{\}}_{0\le i<n}\cup \{w_i{\}}_{0\le i<n}$ and edge set $E(G(n,k))=\{v_i{v}_{i+1}{\}}_{0\le i<n}\cup \{w_i{w}_{i+k}{\}}_{0\le i<n}\cup \{v_i{w}_i{\}}_{0\le i<n}$ where the indices are taken modulo $n$. Schwenk found the number of Hamiltonian cycles in $G(n,2)$, and in this article we present initial conditions and linear recurrence relations for the number of Hamiltonian cycles in $G(n,3)$ and $G(n,4)$. This is attained by introducing $G^{\prime }(n,k)$, which is a modified version of $G(n,k)$, and a subset of its subgraphs which we call admissible, and which are partitioned into different classes in such a manner that we can find relations between the number of admissible subgraphs of each class. The classes and their relations define a directed graph such that each strongly connected component is of a manageable size for $k=3$ and $k=4$, which allows us to find linear recurrence relations for the number of admissible subgraphs in each class in these cases. The number of Hamiltonian cycles in $G(n,k)$ is a sum of the number of admissible subgraphs of $G^{\prime }(n,k)$ over a certain subset of the classes.

18 pages, 2 figures (in addition to a table of figures and a flowchart). Current version: Added discussion about writing the number of Hamiltonian cycles as a sum of the nth terms of several sequences, each with a characteristic polynomial of small degree, and fixed some minor issues