The aim of this note is to present a short proof of a result of Nedela and S8 koviera (J. Graph Theory 19 (1995, 1 11)) concerning those generalized Petersen graphs that are also Cayley graphs. In that paper the authors chose the heavy weaponry of regular maps on closed connected orientable surfaces. Our proof relies on the general characterization of Cayley graphs and on the complete determination of the automorphism groups of the generalized Petersen graphs. With both of them in hand, it is easy to find the intersection of the two graph families.
1997 Academic
Press
All graphs and groups considered here will be finite. To begin with, let us recall the definition of a Cayley graph as follows. If G is a group and S G a subset of generators of G, such that 1 Â S and s # S O s &1 # S, then the Cayley graph C(G, S) has G as its vertex-set, while g, h # G are adjacent if and only if g &1 h # S. It is known that these graphs are vertex-transitive; in fact, the following theorem of Sabidussi [7] provides their characterization in terms of regular groups of automorphisms.
Theorem 1 [7, Lemma 4]. A graph X with the vertex-set V is a Cayley graph, if and only if Aut(X ) contains a subgroup which acts regularly on V.
Watkins [9] extended the idea of the infamous'' Petersen graph and defined the infinite family of generalized Petersen graphs, whose definition follows. Let n 3 and k # Z n "[0]. The generalized Petersen graph P(n, k) is the graph on the vertex-set [x i , y i | i # Z n ] with adjacencies x i x i+1 , x i y i , and y i y i+k for all i. We are of course interested in automorphism groups of these graphs, in view of Theorem 1. Denote A(n, k)=Aut(P(n, k)); obviously, A(n, k) contains two elements, : (the rotation'') and ; (the ``reflection''), defined by :(x i ) = x i+1 , :( y i ) = y i+1 , ;(x i ) = x &i , and ;( y i )=y &i . Let # be the permutation of vertices defined by #(x i )=y ki and article no. TB971729 226 0095-8956Â97 25.00