4.2 Cayley graph: judgement

Definition

Let $G$ be a group and $S\subset G$ be a subset of $G$. Define a graph $\Gamma =(V,E)$ where $V=G$ and $E=\{(x,y)\in G\times G:y{x}^{-1}\in S\}$. The graph is called Cayley graph, denoted as $\mathrm{Cay}(G,S)$.

Note

Question: For a given graph $\Gamma$, under what condition $\Gamma$ is a Cayley graph?

TL;DR: Cayley graph is vertex transitive; a graph is Cayley iff its automorphism group has a vertex regular subgroup.

Cayley graph is vertex transitive

Lemma

Cayley graphs are vertex transitive.

\begin{proof} $G⩽\mathrm{Aut}(\Gamma )$ acts on vertex set transitively. \end{proof}

Remark.

• Cayley graph is not necessarily edge transitive, e.g. $C_3\square C_4$. However, maybe most vertex-transitive graphs are Cayley graphs. (Mackey-Praeger)
• Conversely, a vertex transitive graph may not a Cayley graph, e.g. Petersen graph.

Example

Petersen graph is not a Cayley graph.

\begin{proof} Suppose there is a group $G$ and its subset $S$ such that the Petersen graph $\Gamma =\mathrm{Cay}(G,S)$. Then $|G|=10$ and $|S|=3$ yields $G=C_{10}$ or $G=D_{10}$.

Assume $G=C_{10}$. Then $1-a-ab-b-1$ is a circle of length $4$. But in Petersen graph the circle does not exist. Thus $G=D_{10}$.

When $G=D_{10}$, then $|S|$ odd and $\Gamma$ vertex transitive yield $S$ has an involution, i.e. an element whose order is $2$. Then $S$ has a reflection $b$. If $S$ has an element $a$ satisfying $|a|=5$, by $(ab{)}^2=1$ we still has a circle of length 4: $1-a-ab-aba-1$, contradiction. Otherwise all elements of $S$ are involution, then there is no product of 5 generators equal to identity. But Petersen graph has circles of length 5, contradiction. \end{proof}

$\mathrm{Aut}\Gamma$ has a vertex regular subgroup

Theorem

A graph $\Gamma$ is Cayley graph if and only if $\mathrm{Aut}(\Gamma )$ contains a vertex regular subgroup.

\begin{proof} One direction is easy. Now assume $\mathrm{Aut}(\Gamma )$ has a vertex regular subgroup $G$. By $G$ regular on $V$, every vertex can be written as $v=v_0^g$ for a fixed $v_0$ and unique $g\in G$. Then there is a bijection from vertex set to $G$. Define $S=\{g\in G:v_0^g\in \Gamma (v_0)\}$. Then $\Gamma \cong \mathrm{Cay}(G,S)$. \end{proof}

By the above theorem, it’s easy to prove the following corollary:

Corollary

$\Gamma$ is a Cayley graph of $G$ iff $\mathrm{Aut}\Gamma =G(\mathrm{Aut}\Gamma {)}_v$ such that $G\cap (\mathrm{Aut}\Gamma {)}_v=\{id\}$.