4.6 Dual Cayley graph

Definition

Let $\Gamma =\mathrm{Cay}(G,S)$ and let $X\le \mathrm{Aut}\Gamma$ such that $X\ge \hat{G}$. Then $X=\hat{G}{X}_{\alpha }$ where $\alpha =1$ and $\hat{G}\cap X_{\alpha }=\{1\}$.

If $\hat{G}$ is core free in $X$, then $X_{\alpha }$ is a regular permutation group on $\Omega :=[X:\hat{G}]$. Thus there is a Cayley graph of $X_{\alpha }$ whose vertex set is $\Omega$ and automorphism group is $\mathrm{Aut}\Gamma$. We call this graph as dual Cayley graph of $\Gamma$.

Application

Let $G=⟨a,b⟩$ be a simple group where $a^3=b^2=1$. Note that the following theorems have similar arguments.

Thm 1. Let $\Sigma =\mathrm{Cos}(G,⟨a⟩,⟨a⟩b⟨a⟩)$. Then $\Sigma$ is not a Cayley graph with at most a few possible exception.

Thm 2. Let $\Gamma =\mathrm{Cay}(G,\{b,b^a,b^{a^2}\})$. Then either $\mathrm{Aut}\Gamma =\hat{G}:\mathrm{Aut}(G,S)$ or $G$ is a one of 7 small condidates.

Remark of theorem 2. More explicitly, the $7$ condidates are as following: See here.

Sketch of proofs. Consider the fact as follows:

(Tutte’s theorem) If $\Gamma$ is a $G$-arc-transitive cubic graph, then the vertex stabilizer $G_v$ is one of the groups: $Z_3,S_3,S_3\times S_2,S_4,S_4\times S_2$.

Then if $R\le \mathrm{Aut}\Gamma$ is core free in $\mathrm{Aut}\Gamma$, $X_{\alpha }$ acting on $\Omega :=[X:R]$ is regular and so $|X_{\alpha }|=|\Omega |$. $\Omega$ is a vertex set of dual Cayley graph of $\Gamma$ yields $\mathrm{Aut}\Gamma$ is a permutation subgroup of $\Omega$. Then $\mathrm{Aut}\Gamma \le S_{48}$ if $\Gamma$ is a connected cubic arc-transitive graph.

• For the first theorem, assume $\Gamma$ is a Cayley graph on group $R$. If $R$ is core free in $X=\mathrm{Aut}\Gamma$, then we get a dual Cayley graph whose number of vertice is divided by 48 (by Tutte’s thm) and so $G\le X\le S_{48}$. If $R$ is not core free, consider $C=Cor{e}_X(R)$ and $\bar{R}=R/C$ is core free in $\bar{X}=X/C$. Then $G$ simple and $R<G$ yields $\bar{G}=GC/C=G\le \bar{X}\le S_{48}$. So there are finitely many exceptions where $\Gamma$ is a Cayley graph.
• For the second one, if $G$ is not core free in $\mathrm{Aut}\Gamma$, we have done. Otherwise, $G\le \mathrm{Aut}\Gamma \le S_{48}$ yields $G$ has finite possibilities.

Thm. Let $G$ be a non-abelian simple group. Let $\Gamma =\mathrm{Cay}(G,S)$ such that $X=\mathrm{Aut}\Gamma$ is primitive on the vertex set. Then $G⊲\mathrm{Aut}\Gamma$ with finitely many possible exceptions.

Sketch of proof. Similarly, under the condition of ”$X=\mathrm{Aut}\Gamma$ is primitive on the vertex set”, $|X_{\alpha }|\le f(|S|)$, i.e. $\mathrm{Aut}\Gamma$ has a upper bound. Then repeat the argument in the above paragraph.