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. s 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 } and gcd ( n , k ) = 1 , P ( n , k ) is either Hamilton-connected or bipartite and Hamilton-laceable, as long as ( n , k ) ≠ ( 6 r + 5 , 2 ) or ( 5 , 3 ) . For k = 2 , we consider the remaining cases for n and completely determine which pairs of vertices in P ( n , 2 ) are joined by Hamilton paths. However, the main point is to show that, for each k , it is a finite problem to determine, for all n , which pairs of vertices in P ( n , k ) are the ends of a Hamilton path.