View source for Cayley graph

Cayley graphs stem from a type of diagram now called a Cayley colour diagram, which was introduced by A. Cayley in 1878 as a graphic representation of abstract groups. Cayley colour diagrams were used in [[#References|[a7]]] to investigate groups given by generators and relations.

A Cayley colour diagram is a directed graph with coloured edges (cf. also [[Graph, oriented|Graph, oriented]]), and gives rise to a Cayley graph if the colours on the edges are ignored. Cayley colour diagrams were generalized to Schreier coset diagrams by O. Schreier in 1927, and both were investigated as  "graphs"  in [[#References|[a20]]]. Cayley graphs and their generalizations — vertex-transitive graphs — are systematically studied in [[#References|[a5]]], [[#References|[a6]]], [[#References|[a18]]].

Cayley graphs provide graphic representations for abstract groups. They are a bridge between groups and surfaces, and they give rise to examples for various extremal graph problems, and good models for interconnection networks.

Given a [[Group|group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300501.png" /> and a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300502.png" /> which does not contain the identity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300503.png" />, the associated Cayley graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300504.png" /> is the directed graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300505.png" /> with vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300506.png" /> and with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300507.png" /> adjacent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300508.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c1300509.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005010.png" />, then the adjacency relation is symmetric and thus the Cayley graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005011.png" /> may be viewed as an undirected [[Graph|graph]].

Some examples of Cayley graphs are

the well-studied circulant graphs (loop networks) are precisely the Cayley graphs of cyclic groups;

hypercube graphs are Cayley graphs of elementary Abelian <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005012.png" />-groups; more generally,

Hamming graphs are Cayley graphs of elementary Abelian groups.

By definition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005013.png" /> has out-valency <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005014.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005015.png" /> is connected if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005016.png" />. Further, the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005017.png" /> acting by right multiplication (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005018.png" />) is a subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005019.png" /> and acts regularly on the vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005020.png" /> (cf. also [[Regular group|Regular group]]). Thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005021.png" /> contains a subgroup which is regular on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005022.png" /> and isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005023.png" />. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005024.png" /> is transitive on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005025.png" />, and so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005026.png" /> is vertex-transitive. It was shown in [[#References|[a20]]] that an arbitrary graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005027.png" /> is a Cayley graph of a group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005028.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005029.png" /> contains a regular subgroup isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005030.png" />. Identifying the regular subgroup with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005031.png" />, one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005032.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005033.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005034.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005035.png" />, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005036.png" /> is factorizable. Some part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005037.png" /> can be described in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005038.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005039.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005040.png" />. So, part of the information about the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005041.png" /> (which may be available from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005042.png" />) may be directly read from information about the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005043.png" />.

Some work has been devoted to characterizing Cayley graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005044.png" /> in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005045.png" />. See [[#References|[a19]]], [[#References|[a21]]] for the study of edge-transitive Cayley graphs, and [[#References|[a4]]], [[#References|[a14]]] for determining isomorphism relations between Cayley graphs of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005046.png" />. The extreme case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005047.png" /> has received considerable attention, see [[#References|[a5]]], [[#References|[a10]]], [[#References|[a15]]].

Cayley graphs contain long paths (see [[#References|[a5]]]), and have many other nice combinatorial properties (see [[#References|[a5]]]). Cayley graphs have been used to construct extremal graphs: see [[#References|[a16]]], [[#References|[a13]]] for the constructions of Ramanujan graphs and expanders; see [[#References|[a1]]], [[#References|[a17]]] for the constructions of graphs without short cycles. They have also been used to construct other combinatorial structures: see [[#References|[a12]]], [[#References|[a8]]] for the constructions of various communication networks; see [[#References|[a2]]] for difference sets in design theory.

Cayley graphs have been used to analyse algorithms for computing with groups, see [[#References|[a5]]]. For infinite groups, Cayley graphs provide convenient metric diagrams for words in the corresponding groups, and underlie the study of growth of groups, see [[#References|[a5]]], [[#References|[a11]]].

Cayley maps are Cayley graphs embedded into certain surfaces, and provide pictorial representations of groups and group actions on surfaces. They have been extensively studied, see [[#References|[a3]]], [[#References|[a9]]].

Cayley graphs form a proper subclass of the vertex-transitive graphs. The [[Petersen graph|Petersen graph]] is the smallest vertex-transitive graph which is not a Cayley graph. B. McKay, C.E. Praeger and G.F. Royle observed that most vertex-transitive graphs of order at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c130/c130050/c13005048.png" /> are Cayley graphs, and this led McKay and Praeger to conjecture (1994) that most vertex-transitive graphs are Cayley graphs, see [[#References|[a18]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N. Alon,   "Tools from higher algebra" , ''Handbook of Combinatorics'' , Elsevier  (1995)  pp. 11751–1783</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T. Beth,   D. Jungnickel,   H. Lenz,   "Design theory" , '''I''' , Cambridge Univ. Press  (1999)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. Biggs,   A.T. White,   "Permutation groups and combinatorial structures" , ''Math. Soc. Lecture Notes'' , '''33''' , Cambridge Univ. Press  (1979)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L. Babai,   "Isomorphism problem for a class of point-symmetric structures"  ''Acta Math. Acad. Sci. Hungar.'' , '''29'''  (1977)  pp. 329–336</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  L. Babai,   "Automorphism groups, isomorphism, reconstruction" , ''Handbook of Combinatorics'' , Elsevier  (1995)  pp. 1449–1540</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  N. Biggs,   "Algebraic graph theory" , Cambridge Univ. Press  (1992)  (Edition: Second)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  H.S.M. Coxeter,   W.O.J. Moser,   "Generators and relations for discrete groups" , Springer  (1957)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  X.G. Fang,   C.H. Li,   C.E. Praeger,   "On orbital regular graphs and Frobenius graphs"  ''Discr. Math.'' , '''182'''  (1998)  pp. 85–99</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.L. Gross,   T.W. Tucher,   "Topological graph theory" , Wiley  (1987)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  C.D. Godsil,   "On the full automorphism group of a graph"  ''Combinatorica'' , '''1'''  (1981)  pp. 243–256</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  M. Gromov,   "Groups of polynomial growth and expanding maps"  ''Publ. Math. IHES'' , '''53'''  (1981)  pp. 53–73</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  R. Heydemann,   B. Ducourthial,   "Cayley graphs and interconnection networks" , ''Graph Symmetry: Algebraic Methods and Applications'' , ''NATO Ser. C'' , '''497''' , Kluwer Acad. Publ.  (1997)  pp. 167–224</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  A. Lubotzky,   R. Phillips,   P. Sarnak,   "Ramanujan graphs"  ''Combinatorica'' , '''8'''  (1988)  pp. 261–277</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  C.H. Li,   "Finite CI-groups are soluble"  ''Bull. London Math. Soc.'' , '''31'''  (1999)  pp. 419–423</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  C.H. Li,   "The solution of a problem of Godsil regarding cubic Cayley graphs"  ''J. Combin. Th. B'' , '''72'''  (1998)  pp. 140–142</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  A. Lubotzky,   "Discrete groups, expanding graphs and invariant measures" , ''Progress in Math.'' , '''125''' , Birkhäuser  (1994)</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  G.A. Margulis,   "Explicit constructions of graphs without short cycles and low density codes"  ''Combinatorica'' , '''2'''  (1982)  pp. 71–78</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  C.E. Praeger,   "Finite transitive permutation groups and finite vertex-transitive graphs" , ''Graph Symmetry: Algebraic Methods and Applications'' , ''NATO Ser. C'' , '''497''' , Kluwer Acad. Publ.  (1997)  pp. 277–318</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  C.E. Praeger,   "Finite normal edge-transitive Cayley graphs"  ''Bull. Austral. Math. Soc.'' , '''60'''  (1999)  pp. 207–220</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  G.O. Sabidussi,   "Vertex-transitive graphs"  ''Monatsh. Math.'' , '''68'''  (1964)  pp. 426–438</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  M.Y. Xu,   "Automorphism groups and isomorphisms of Cayley digraphs"  ''Discr. Math.'' , '''182'''  (1998)  pp. 309–320</TD></TR></table>