In mathematics, a Cayley graph, named after Arthur Cayley, is a graph theory that encodes the structure of a group (mathematics). It is a central tool in combinatorial group theory and geometric group theory.

Let G be a group, and let S be a generating set of a group for G. The Cayley graph of G with respect to S has a vertex for every element of G, with an edge from g to gs for all elements gin G and sin S.

= Example =

For example, the Cayley graph of the free group on two generators a and b is depicted to the right. (Note that e represents the identity element.) Travelling right along an edge represents multiplying on the right by a, while travelling up corresponds to multiplying by b. Since the free group has no relation (mathematics)s, the graph has no cycles.

= Variations =

The above definition gives a connected, directed graph. There are a number of slight variations on the definition:

#Usually S is not allowed to contain the identity element e. #If the set S doesn t generate the whole group, the Cayley graph isn t connected. #In some contexts, left multiplication is used instead of right. That is, edges go from g to sg. #In many contexts, the generating set is assumed to be symmetric , meaning that s^{-1} is in S whenever s is. In this case, the graph is undirected.

= The Sabidussi Theorem =

G group action on itself by multiplication on the left. This action induces an action of G on its Cayley graph. Explicitly, an element h sends a vertex g to the vertex hg, and the edge (g,gs) to the edge (hg,hgs). Since the action of G on itself is transitive, any Cayley graph is vertex-transitive. The Sabidussi theorem gives a characterization of Cayley graphs: Graph X is a Cayley graph if and only if the automorphism group of X contains a subgroup G acting regularly on the vertex set of X.

= Schreier coset graph =

If one takes the vertices to instead be right cosets of a fixed subgroup H, one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd-Coxeter process.

= Connection to graph theory =

Insights into the structure of the group can be obtained by studying the adjacency matrix of the graph and in particular applying the theorems of spectral graph theory.

A standard Cayley graph for the direct product of groups is the cartesian product of the corresponding Cayley graphs. For instance, a cycle graph C_n is a Cayley graph for the cyclic group Z_n. Therefore the cartesian product C_n square C_m , (an n by m grid on torus) is a Cayley graph for the direct product Z_n imes Z_m.

= See also =