Which generalized petersen graphs are cayley graphs

Note that the graph GI n ; J will be vertex-transitive if we are able to permute the layers of GI n ; J transitively among themselves. Then GI n ; J is vertex - transitive. An example is given in Fig. The graph GI 5;1,1,2 in a has 5-cycles as its three layers but is not vertex-transitive, while the graph GI 7;1,2,3 in b is vertex-transitive and has two edge orbits. First, it was shown in [ 6 ] that GI 10;1,2 is vertex-transitive. Hence we may assume that X has no skew automorphism, and therefore every automorphism of X preserves the fundamental edge-partition.

Now because X is vertex-transitive, and the layer L 0 is a single n -cycle, it follows that all the layers of X must be cycles, and so every element of J must be coprime to n , and therefore a unit mod n. We will now find some other examples, and show that every vertex-transitive GI -graph has a special form.

To do that, we introduce some more notation: we denote by [ k ] J the concatenation of k copies of the multiset J. Note that this may involve a non-standard ordering of the elements of [ k ] J , but it makes the proofs of some things in this and the next section easier to explain—specifically, Theorem 19 and Lemmas 21 and We can now prove a , by extending certain automorphisms of X to automorphisms of Y that make it vertex-transitive.

Thus b holds in all eight cases, and so from now on, we may assume that X is not edge-transitive, and hence that every automorphism of X respects the fundamental edge-partition. So now suppose that not all elements of J are the same. The set J 0 is primitive since it contains 1 and all of its elements are distinct. To finish the proof, all we have to do is show that GI n ; J 0 is vertex-transitive.

Note that the above theorem applies only to connected GI -graphs. Disconnected vertex-transitive GI -graphs are just disjoint unions of connected vertex-transitive GI -graphs, and can be dealt with accordingly. We finish this section with observations about the graphs GI 5;1,2 and GI 10;1,2.

The Petersen graph GI 5;1,2 is vertex-transitive, and its automorphism group acts transitively on the two layers; in fact so does a subgroup of order 20 which preserves the set of its ten layer edges. On the other hand, the automorphism group of the dodecahedral graph GI 10;1,2 has no layer-transitive subgroup preserving the set of layer edges and the set of spoke edges , and so the above theorem does not apply to it.

First, a Cayley graph Cay G , S is a graph whose vertices can be labelled with the elements of some group G , and whose edges correspond to multiplication by the elements of some subset S or their inverses.

Alternatively, a Cayley graph is any regular graph X whose automorphism group has a subgroup G that acts regularly on vertices. Note that under both definitions, the Cayley graph is connected if and only if the set S generates the group G.

Also note that every Cayley graph is vertex-transitive by definition , and that every non-trivial element of the subgroup G fixes no vertices of the graph. We will assume that X is connected, because if it is not, then it is simply a disjoint union of isomorphic copies of a connected smaller example.

Also we will suppose that X is not GI 10;1,2 , for reasons related to Theorem In fact, of the seven generalized Petersen graphs among the eight edge-transitive GI -graphs listed in Theorem 5, it is known by the main result of [ 18 ] or [ 14 ] that G 4,1 , G 8,3 , G 12,5 and G 24,5 are Cayley graphs, while G 5,2 , G 10,2 and G 10,3 are not. Most of this and the fact that the eighth edge-transitive graph GI 3;1,1,1 is a Cayley graph will actually follow from what we prove below.

Consider the case where J is primitive as we defined in Sect. The graph GI 10;1,2 is not a Cayley graph, for other reasons. Also by what we found in Sect. Note that this shows, for example, that both of the remaining two edge-transitive GI -graphs GI 4;1,1 and GI 3;1,1,1 are Cayley graphs. Since R acts regularly on vertices, every non-trivial automorphism in R has to be semi-regular.

The family of GI -graphs forms a natural generalization of the Petersen graph. Our initial studies of GI -graphs have shown that this family is indeed very interesting and deserves further consideration.

These graphs are also related to circulant graphs [ 17 ]. Through that relationship, we were able to solve the puzzle of what appeared to be unstructured automorphisms of GI -graphs, and this enabled us to find their automorphism groups and classify those that are vertex-transitive or Cayley graphs. Symmetries of graphs offer additional interesting questions and may open new viewpoints in the study of the structure of graphs.

For instance, it would be interesting to investigate consistent cycles of GI -graphs. Consistent cycles were introduced by John H. Conway in a talk in ; for a recent reference on this topic, see [ 16 ]. Let us mention also the problem of unit-distance drawings of GI -graphs. A graph is a unit-distance graph if it can be drawn in the plane such that all of its edges have the same length.

In [ 10 ], it was shown that all I -graphs are unit-distance graphs. On the other hand, obviously no GI -graph with four or more layers can be a unit-distance graph, since it contains a K 4 as a subgraph, which itself is not a unit-distance graph.

Hence the only open case of interest is the sub-class of GI -graphs having three layers. We know of only one other connected example that is a unit-distance graph, and it is remarkable.

This is the graph GI 7;1,2,3 , which is shown in Fig. One can then verify that all edges have the same length 1. Its girth is 3 but it contains no cycles of length 4. This means that its Kronecker cover see [ 12 ] has girth 6 and is a Levi graph [ 3 , 20 ] of a self-polar, point- and line-transitive but not flag-transitive combinatorial 21 4 -configuration.

Boben, M. Bosma, W. Coxeter, H. Bouwer, I. Charles Babbage Research Centre Frucht, R. Harary, F. Addison-Wesley, Reading Google Scholar. Horvat, B. Discrete Math. Korean Math. Graphs Comb. Imrich, W. Theory, Ser. B 69 , — Ars Math. Morris, J. Nedela, R. Graph Theory 19 , 1—11 Pisanski, T.

Watkins, M. Theory 6 , — Download references. Marsden Fund via grant UOA You can also search for this author in PubMed Google Scholar. Correspondence to Marston D.

Reprints and Permissions. Conder, M. GI -graphs: a new class of graphs with many symmetries. J Algebr Comb 40, — Download citation. Received : 04 September Accepted : 08 October Published : 30 October Issue Date : August Anyone you share the following link with will be able to read this content:.

Sorry, a shareable link is not currently available for this article. Provided by the Springer Nature SharedIt content-sharing initiative. Skip to main content. Search SpringerLink Search. Download PDF. John D. Wiley Graph theory Cubic function. Citation Type. Has PDF. Publication Type. More Filters. Decomposition of generalized Petersen graphs into claws, cycles and paths. GI-graphs and their groups. The class of generalized Petersen graphs was introduced by Coxeter in the s.

Frucht, Graver and Watkins determined the automorphism groups of generalized Petersen graphs in , and much later, … Expand. View 2 excerpts, cites background. GI-graphs: a new class of graphs with many symmetries. A complete classification of cubic symmetric graphs of girth 6. Cubic vertex-transitive graphs of order 2pq.

A graph is vertex-transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a … Expand. On cubic non-Cayley vertex-transitive graphs. On the minimum vertex cover of generalized Petersen graphs. A family of non-Cayley cores based on vertex-transitive or strongly regular self-complementary graphs.

View 1 excerpt, cites background. Diameter of generalized Petersen graphs. Due to their broad application to different fields of theory and practice, generalized Petersen graphs GPG n, s have been extensively investigated. Despite the regularity of generalized Petersen … Expand. View 3 excerpts. In a class of generalized Petersen graphs was introducedby Coxeter and around popularized by Frucht, Graver and Watkins.

The family of I-graphs mentioned in by Bouwer et al. The classification of hamiltonian generalized Petersen graphs. The groups of the generalized Petersen graphs. It is shown that if a graph is vertex- and edge-transitive of odd valence, has at least 5 vertices, and is not bipartite, then its derived line graph is not a Cayley graph.