Hamilton paths in generalized Petersen graphs

Alspach and Qin proved that connected Cayley graphs of Hamiltonian groups (all subgroups are normal) are either Hamilton-connected (every pair of vertices is joined by a Hamilton path), or are bipartite and Hamilton-laceable (every pair on opposite sides of the bipartition are joined by a Hamilton path). Their proof made use of Hamilton-connectedness of certain Generalized Petersen graphs.In this work, we extend (and make a small correction to) the results of Alspach and Liu on Hamilton paths in generalized Petersen graphs. Alspach and Liu showed that, for k∈{1,2,3}k∈{1,2,3} and gcd(n,k)=1gcd(n,k)=1, P(n,k)P(n,k) is either Hamilton-connected or bipartite and Hamilton-laceable, as long as (n,k)≠(6r+5,2)(n,k)≠(6r+5,2) or (5,3)(5,3). For k=2k=2, we consider the remaining cases for nn and completely determine which pairs of vertices in P(n,2)P(n,2) are joined by Hamilton paths. However, the main point is to show that, for each kk, it is a finite problem to determine, for all nn, which pairs of vertices in P(n,k)P(n,k) are the ends of a Hamilton path.