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 [a7] to investigate groups given by generators and relations.

A Cayley colour diagram is a directed graph with coloured edges (cf. also 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 [a20]. Cayley graphs and their generalizations — vertex-transitive graphs — are systematically studied in [a5], [a6], [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 $G$ and a subset $S \subset G$ which does not contain the identity of $G$, the associated Cayley graph $\operatorname { Cay } ( G , S )$ is the directed graph $\Gamma$ with vertex set $G$ and with $x$ adjacent to $y$ if and only if $y x ^ { - 1 } \in S$. If $S = S ^ { - 1 } : = \left\{ s ^ { - 1 } : s \in S \right\}$, then the adjacency relation is symmetric and thus the Cayley graph $\operatorname { Cay } ( G , S )$ may be viewed as an undirected 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 $2$-groups; more generally,

Hamming graphs are Cayley graphs of elementary Abelian groups.

By definition, $\Gamma = \operatorname { Cay } ( G , S )$ has out-valency $|S|$, and $\Gamma$ is connected if and only if $\langle S \rangle = G$. Further, the group $G$ acting by right multiplication (that is, $g : x \rightarrow x g$) is a subgroup of $\operatorname{Aut} \Gamma$ and acts regularly on the vertex set $V \Gamma = G$ (cf. also Regular group). Thus $\operatorname{Aut} \Gamma$ contains a subgroup which is regular on $V \Gamma$ and isomorphic to $G$. In particular, $\operatorname{Aut} \Gamma$ is transitive on $V \Gamma$, and so $\Gamma$ is vertex-transitive. It was shown in [a20] that an arbitrary graph $\Gamma$ is a Cayley graph of a group $G$ if and only if $\operatorname{Aut} \Gamma$ contains a regular subgroup isomorphic to $G$. Identifying the regular subgroup with $G$, one has

\begin{equation*} \operatorname{Aut} \Gamma = GH, \end{equation*}

\begin{equation*} G \bigcap H = 1, \end{equation*}

where $H = \{ \sigma \in \operatorname { Aut } \Gamma : v ^ { \sigma } = v \}$ for some $v \in V \Gamma$, i.e., $\operatorname{Aut} \Gamma$ is factorizable. Some part of $\operatorname{Aut} \Gamma$ can be described in terms of $\operatorname{Aut}( G )$:

\begin{equation*} \mathcal{N} _ { \operatorname{Aut} \Gamma } ( G ) = G . \operatorname { Aut } ( G , S ), \end{equation*}

where $\operatorname { Aut } ( G , S ) = \{ \sigma \in \operatorname { Aut } ( G ) : S ^ { \sigma } = S \}$. So, part of the information about the graph $\Gamma$ (which may be available from $\operatorname{Aut} \Gamma$) may be directly read from information about the group $G$.

Some work has been devoted to characterizing Cayley graphs $\Gamma = \operatorname { Cay } ( G , S )$ in terms of $\operatorname{Aut}( G )$. See [a19], [a21] for the study of edge-transitive Cayley graphs, and [a4], [a14] for determining isomorphism relations between Cayley graphs of $G$. The extreme case where $\operatorname{Aut} \Gamma = G$ has received considerable attention, see [a5], [a10], [a15].

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

Cayley graphs have been used to analyse algorithms for computing with groups, see [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 [a5], [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 [a3], [a9].

Cayley graphs form a proper subclass of the vertex-transitive graphs. The 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 $24$ are Cayley graphs, and this led McKay and Praeger to conjecture (1994) that most vertex-transitive graphs are Cayley graphs, see [a18].

References

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