structural:summarization, structural:scholar_edition, linguistic:paraphrasing, stylistic:style_transfer, quality:correction
Characterization

The group G {\displaystyle G} acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of G {\displaystyle G} on its Cayley graph. Explicitly, an element h ∈ G {\displaystyle h\in G} maps a vertex g ∈ V (Γ) {\displaystyle g\in V(\Gamma)} to the vertex h g ∈ V (Γ). {\displaystyle hg\in V(\Gamma).} The set of edges of the Cayley graph and their color is preserved by this action: the edge (g, g s) {\displaystyle (g,gs)} is mapped to the edge (h g, h g s) {\displaystyle (hg,hgs)}, both having color c s {\displaystyle c_{s}}. In fact, all automorphisms of the colored directed graph Γ {\displaystyle \Gamma } are of this form, so that G {\displaystyle G} is isomorphic to the symmetry group of Γ {\displaystyle \Gamma }.

The left multiplication action of a group on itself is simply transitive, in particular, Cayley graphs are vertex-transitive. The following is a kind of converse to this:

Sabidussi's Theorem — An (unlabeled and uncolored) directed graph Γ {\displaystyle \Gamma } is a Cayley graph of a group G {\displaystyle G} if and only if it admits a simply transitive action of G {\displaystyle G} by graph automorphisms (i.e., preserving the set of directed edges).

To recover the group G {\displaystyle G} and the generating set S {\displaystyle S} from the unlabeled directed graph Γ {\displaystyle \Gamma }, select a vertex v 1 ∈ V (Γ) {\displaystyle v_{1}\in V(\Gamma)} and label it by the identity element of the group. Then label each vertex v {\displaystyle v} of Γ {\displaystyle \Gamma } by the unique element of G {\displaystyle G} that maps v 1 {\displaystyle v_{1}} to v. {\displaystyle v.} The set S {\displaystyle S} of generators of G {\displaystyle G} that yields Γ {\displaystyle \Gamma } as the Cayley graph Γ (G, S) {\displaystyle \Gamma (G,S)} is the set of labels of out-neighbors of v 1 {\displaystyle v_{1}}. Since Γ {\displaystyle \Gamma } is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of G {\displaystyle G} which permute S {\displaystyle S}.