TOPICS
Search

Cayley Graph


CayleyGraph

Let G be a group, and let S subset= G be a set of group elements such that the identity element I not in S. The Cayley graph associated with (G,S) is then defined as the directed graph having one vertex associated with each group element and directed edges (g,h) whenever gh^(-1) in S. The Cayley graph may depend on the choice of a generating set, and is connected iff S generates G (i.e., the set S are group generators of G).

Care is needed since the term "Cayley graph" is also used when S is implicitly understood to be a set of generators for the group, in which case the graph is always connected (but in general, still dependent on the choice of generators). This sort of Cayley graph of a group G may be computed in the Wolfram Language using CayleyGraph[G], where the generators used are those returned by GroupGenerators[G].

To complicate matters further, undirected versions of proper directed Cayley graphs are also known as Cayley graphs.

An undirected Cayley graph of a particular generating set of the alternating group A_n is sometimes known as a alternating group graph. The Cayley graph of the cyclic group C_n is the cycle graph C_n, and of the dihedral group D_n is the prism graph Y_n. Other classes of graphs that are Cayley graphs are circulant graphs (connected if requiring a generating set; possibly disconnected if not), cube connected cycles, Hamming graphs, and hypercube graphs.

A directed graph Cayley graph has the same edge multiplicity for each node. A (directed or undirected) Cayley graph is always vertex-transitive, but the converse need not hold. However, a large fraction of small vertex-transitive graphs are Cayley graphs (McKay and Royle 1990).

Royle maintains a list of not-necessarily-connected vertex-transitive graphs with Cayley or non-Cayley designations up to 31 vertices and although the values for 27, 28 and 30 vertices have not been independently verified (though an error in the groups can only affect the graphs if somehow a minimal transitive group has been omitted, so errors are unlikely). The numbers of not-necessarily-connected Cayley graphs on n=1, 2, ... nodes are 1, 2, 2, 4, 3, 8, 4, 14, 9, 20, 8, 74, ... (OEIS A185959; McKay and Royle 1990, McKay and Praeger 1994), and the numbers of nodes on which non-Cayley vertex-transitive graphs exist are 10, 15, 16, 18, 20, 24, 26, 28, 30, ....

The smallest vertex-transitive non-Cayley graph is the Petersen graph P (McKay and Praeger 1994) and the smallest disconnected vertex-transitive non-Cayley graph is two copies of P.

CayleyGraphCubical

Cayley graphs can be generated by starting with a set of generator permutations {P_i} (which does not include the identity permutation) and mutually permuting elements until no new permutations are reached. This produces a set S that is closed under permutations of elements. Connecting each pair of permutations (P_i,P_j) with an edge if P_k(P_i)=P_j for some P_k in S then gives a Cayley graph.

The only groups that can give planar Cayley graphs are exactly Z_n, Z_2×Z_n, D_n, S_4, A_4, and A_5, as proved by Maschke (1896).

The following table lists some graphs that are undirected versions of Cayley graphs generated by small numbers of small permutations.

graphgenerators
16-cell graph{{1,2,4,3}, {2,1,3,4}, {2,1,4,3}, {3,4,1,2}, {3,4,2,1}}
circulant graph Ci_(12)(1,3){{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}, {2,1,5,4,3}}
complete bipartite graph K_(4,4){{1,2,4,3}, {2,1,3,4}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {3,4,1,2}, {4,3,2,1}}
{{1,2,4,5,6,3}, {2,1,4,5,6,3}}
complete graph K_6{{1,3,2}, {2,1,3}, {2,3,1}, {3,2,1}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,3,2}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, {1,4,3,2}}
cubical graph{{1,2,4,3}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {3,4,1,2}}
{{1,2,3,5,4}, {1,4,5,3,2}}
cubic symmetric graph F_(24)A{{1,2,4,3}, {1,3,2,4}, {3,2,1,4}}
{{1,2,3,4,6,5}, {2,5,4,6,3,1}}
cubic symmetric graph F_(60)A{{1,3,2,5,4}, {2,1,4,3,5}, {4,5,3,1,2}}
cubic vertex-transitive graph Ct19{{1,2,3,4,6,5}, {1,2,4,3,6,5}, {5,6,3,4,1,2}}
cubic vertex-transitive graph Ct23{{1,2,3,4,6,5}, {2,3,1,5,6,4}}
cubic vertex-transitive graph Ct28{{1,3,2,5,4}, {2,3,4,1,5}}
cubic vertex-transitive graph Ct37{{1,2,4,3}, {1,3,2,4},{3,4,1,2}}
cubic vertex-transitive graph Ct38{{1,2,3,4,5,7,6}, {2,3,1,6,7,4,5}}
cubic vertex-transitive graph Ct41{{1,2,4,3}, {1,3,2,4},{2,1,4,3}}
cubic vertex-transitive graph Ct42{{1,2,3,4,5,7,6}, {2,3,4,1,6,5,7}}
cuboctahedral graph{{1,3,4,2}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,3,1,4}, {3,1,2,4}}
{{1,2,4,5,3}, {1,3,4,2,5}}
5-cycle graph{{2,3,4,5,1}, {5,1,2,3,4}}
6-cycle graph{{1,3,2}, {2,1,3}}
{{1,2,4,3}, {1,3,2,4}}
{{1,2,3,5,4}, {1,2,4,3,5}}
8-cycle graph{{1,2,4,3}, {3,4,1,2}}
{{1,2,3,5,4}, {1,4,5,2,3}}
10-cycle graph{{1,3,2,5,4}, {2,1,4,3,5}}
12-cycle graph{{1,2,3,5,4}, {2,1,4,3,5}}
Franklin graph{{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}}
{{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,2,4,3,5,7,6}}
great rhombicuboctahedral graph{{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,3,2,5,4,7,6}}
icosahedral graph{{1,3,4,2}, {2,1,4,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}, {3,1,2,4}}
4-Möbius ladder{{1,2,4,3}, {2,1,4,3}, {3,4,1,2}}
octahedral graph{{1,3,2}, {2,1,3}, {2,3,1}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}}
{{1,2,4,5,3}, {2,1,4,5,3}}
{{1,2,4,5,3}, {2,1,4,5,3}}
Pappus graph{{1,2,3,4,6,5}, {2,3,1,5,4,6}}
2-path graph{{2,1}}
{{1,3,2}}
pentatope graph{{2,3,4,5,1}, {3,4,5,1,2}}
5-prism graph{{1,3,2,5,4}, {2,4,1,5,3}}
{{1,3,2,5,4}, {2,4,1,5,3}}
6-prism graph{{1,2,3,5,4}, {2,1,4,5,3}}
{{1,2,3,5,4}, {2,1,4,5,3}}
small rhombicosidodecahedral graph{{1,2,4,5,3}, {3,4,2,5,1}}
small rhombicuboctahedral graph{{1,3,4,2}, {2,3,4,1}}
{{1,3,4,2}, {1,4,2,3}, {2,3,4,1}}
{{1,3,4,2}, {1,4,2,3}, {2,3,4,1}, {4,1,2,3}}
{{1,2,4,5,3}, {1,3,4,5,2}}
snub cubical graph{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}}
{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}}
{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}, {4,1,2,3}}
square antiprism graph{{1,2,4,3}, {3,4,1,2}, {3,4,2,1}}
{{1,2,4,3}, {3,4,1,2}, {3,4,2,1}, {4,3,1,2}}
square graph{{1,2,4,3}, {2,1,3,4}}
{{1,2,3,5,4}, {1,3,2,4,5}}
tesseract graph{{1,2,3,4,6,5}, {1,2,4,3,5,6}, {3,4,2,1,5,6}}
tetrahedral graph{{2,1,4,3}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {2,1,4,3}}
{{1,3,2,5,4}, {1,4,5,3,2}}
triangle graph{{2,3,1}}
{{1,3,4,2}, {1,4,2,3}}
{{1,2,4,5,3}, {1,2,5,3,4}}
triangular prism graph{{1,3,2}, {2,3,1}}
{{1,2,4,3}, {1,3,4,2}}
{{1,2,4,3}, {1,3,4,2}, {1,4,2,3}}
{{1,2,3,5,4}, {1,2,4,5,3}}
truncated cubical graph{{1,2,4,3}, {2,3,1,4}}
{{1,2,4,3}, {2,3,1,4}, {3,1,2,4}}
{{1,2,3,5,4}, {1,3,4,2,5}}
truncated dodecahedral graph{{1,2,4,5,3}, {3,4,1,2,5}}
truncated icosahedral graph{{1,3,2,5,4}, {2,3,4,5,1}}
truncated octahedral graph{{1,2,4,3}, {2,3,4,1}}
{{1,2,4,3}, {1,3,2,4}, {2,1,3,4}}
{{1,2,3,5,4}, {1,3,4,5,2}}
truncated tetrahedral graph{{1,3,4,2}, {2,1,4,3}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}}
{{1,2,4,5,3}, {1,3,2,5,4}}
utility graph K_(3,3){{1,3,2}, {2,1,3}, {3,2,1}}
{{1,2,4,3}, {1,3,2,4}, {1,4,3,2}}
{{1,2,3,5,4}, {2,3,1,5,4}}
{{1,2,3,5,4}, {2,3,1,5,4}}
CayleyGraphD7

For example, the dihedral group D_7 is a permutation group on 14 elements that can be generated by two elements corresponding to a reversal and a rotation, respectively. Therefore, any two such elements give a connected Cayley graph that has 14 nodes and 28 edges. The left figure above shows the Cayley graph for the choice of generators given by (7, 1, 2, 3, 4, 5, 6) and (7, 6, 5, 4, 3, 2, 1), with reversals shown in red and rotations in blue. Any two elements corresponding to a rotation only with give a disconnected graph, and there are exactly 15 pairs of such elements since there are (6; 2) ways to pick two elements from a six possible rotations. (Here, the number 6 appears instead of 7 since the unit element may not be a member of the subset giving the Cayley graph.) The right figure shows the Cayley graph for D_7 generated by the elements (7, 1, 2, 3, 4, 5, 6) and (6, 7, 1, 2, 3, 4, 5), which is disconnected since these elements do not generate the group (in particular, without a flip, there is no way for permutations with positive order to switch to a negative order; hence two independent rings are obtained).

CayleyGraphA4

The figure above shows the Cayley graph for the alternating group A_4 using the elements (2, 1, 4, 3) and (2, 3, 1, 4) as generators, which is a directed form of the truncated tetrahedral graph.

CayleyGraphK4

If three vertices of the complete graph K_4 are covered with differently colored stones and any stone may be moved to the empty vertex, then the graph of all positions forms a Cayley graph with edges indicating neighboring positions (left figure). This corresponds to the Cayley graph of the symmetric group S_4 using the elements (2, 1, 3, 4), (3, 2, 1, 4), and (4, 2, 3, 1) as generators. It turns out that this graph is a directed version of the unique cubic symmetric graph on 24 vertices (right figure).

Royle has constructed all cubic Cayley graphs up to 1000 vertices, excluding those on 512 and 768 vertices.

Cayley graphs

The Cayley graphs of infinite groups provide interesting geometries. For example, the Cayley graphs of the free group on two generators are illustrated above (drawn out to successive levels), representing horizontal and vertical displacement respectively. Each new edge is drawn at half the size to give fractal images.


See also

Alternating Group Graph, Cage Graph, Cayley Tree, Discrete Group, Free Group, Graph, Group, Group Generators, Noncayley Graph, Rubik's Graph, Vertex-Transitive Graph, Tree

Portions of this entry contributed by Todd Rowland

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, pp. 292-293, 1993.Maschke, H. "The Representation of Finite Groups." Amer. J. Math. 16, 156-194, 1896.McKay, B. D. and Praeger, C. E. "Vertex-Transitive Graphs Which Are Not Cayley Graphs. I." J. Austral. Math. Soc. Ser. A 56, 53-63, 1994.McKay, B. D. and Royle, G. "Construction of All Simple Graphs with at Most 26 Vertices and Transitive Automorphism Group." Ars. Combin. 30, 161-176, 1990.Royle, G. "Cayley Graphs." http://school.maths.uwa.edu.au/~gordon/remote/cayley/.Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Sloane, N. J. A. Sequence A185959 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 938, 2002.

Referenced on Wolfram|Alpha

Cayley Graph

Cite this as:

Pegg, Ed Jr.; Rowland, Todd; and Weisstein, Eric W. "Cayley Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CayleyGraph.html

Subject classifications