Generalizing the generalized Petersen graphs

The generalized Petersen graphs (GPGs) which have been invented by Watkins, may serve for perhaps the simplest nontrivial examples of "galactic" graphs, i.e. those with a nice property of having a semiregular automorphism. Some of them are also vertex-transitive or even more highly symmetric, and some are Cayley graphs. In this paper, we study a further extension of the notion of GPGs with the emphasis on the symmetry properties of the newly defined graphs. © 2006 Elsevier B.V. All rights reserved.