Cayley graph - Knowlpedia

For a group $G$ and a subset $S\subseteq G$ , the right Cayley directed graph $\operatorname{Cay}(G,S)$ has vertex set $G$ and an edge labelled $s$ from $g$ to $gs$ for every $g\in G$ , $s\in S$ .

When $S=S^{-1}$ and $1\notin S$ , the undirected Cayley graph joins distinct vertices $g,h$ when $g^{-1}h\in S$ ; opposite directed edges are treated as one undirected edge. This gives a simple graph of degree $|S|$ when $S$ is finite.

Connectedness

For the undirected convention, paths from $1$ give words in $S$ . Thus the graph is connected exactly when $S$ generates $G$ . Left multiplication by any element of $G$ is a graph automorphism, since it preserves $g^{-1}h$ .

For example, $G=\mathbb Z/m\mathbb Z$ and $S=\{1,-1\}$ give the cycle on $m$ vertices when $m\ge3$ .

Conventions

Left Cayley graphs use edges $g\mapsto sg$ . Generating multisets, the identity generator, and directed generators can produce multiplicities or loops, so those conventions must be specified separately. Some finite Cayley graphs satisfy the Ramanujan spectral bound.