5.1 non-Cayley number

Def. A positive integer $n$ is called a non-Cayley number if there exist vertex-transitive graphs of order $n$ which are not Caley graphs. Denote the set of non-Cayley numbers by $\mathcal{N}\mathcal{C}$.

Exm.

• $n=10$ is a non-Cayley number as Peterson graph is vertex transitive but not a Cayley graph.
• $\left(\genfrac{}{}{0ex}{}{2k+1}{k}\right)\in \mathcal{N}\mathcal{C}$ for $k\ge 2$.
• Primes are not in $\mathcal{N}\mathcal{C}$.

Problem: Characterize members of $\mathcal{N}\mathcal{C}$.

Thm. (D.Marusic, 1983) $p^2$ and $p^3$ are not in $\mathcal{N}\mathcal{C}$.

Here we prove that $p^2\notin \mathcal{N}\mathcal{C}$ as homework.

Thm. (McKay-Praeger, 1994 & 1996): except for $12$, $p^2$ and $p^3$, each non-squarefree number is in $\mathcal{N}\mathcal{C}$.

The above theorem reduce the Problem to Characterize squarefree members of $\mathcal{N}\mathcal{C}$.

Let $\Gamma =(V,E)$ be a connected vertex transitive graph of order $n$ where $n$ is a squarefree integer. Then

• either $\Gamma$ is a non-Cayley graph,
• or $\Gamma$ is a metacirculant (a Cayley graph of a metacyclic group).

If $G$ has a squarefree order, then $G$ is metacyclic (HW). In general, if each Sylow subgroup of $G$ is cyclic, then $G$ is metacyclic. Additionally, if each Sylow subgroup of $G$ is metacyclic, then what is $G$? (it has been characterized.)

Further if we suppose $n$ is an integer such that $(n,\varphi (n))=1$. Then

• either $\Gamma$ is a non-Cayley graph
• or $\Gamma$ is circulant (a Cayley graph of cyclic group).

An oberservation to draw the above conclusion: If $|G|=n$ such that $(n,\varphi (n))=1$ then $n$ is squarefree and $G$ is cyclic.(HW)

fact: If a Sylow $p$-subgroup of a group G is in the center of its normalizer then $G$ has a normal $p$ complement.

Thm. Let $p$ and $q$ be primes such that $p^2|(q-1)$, then $pq\in \mathcal{N}\mathcal{C}$.

Proof. We need to construct a graph of order $pq$ which is vertex transitive and non-Cayley. Next, we construct a coset graph satisfies the requirements.

Let $G=⟨a⟩:⟨b⟩=C_q:C_{p^2}$ is a Frobenius group and $Z(G)=1$. Let $H=⟨b^p⟩\cong C_p$. Let $g=b^a$ and $S=\{g,g^{-1}\}$. Define a coset graph $\Gamma =\mathrm{Cos}(G,H,HSH)$. Then $\Gamma$ is connected (since $g^p=a^{-1}{b}^{p}a$ and $a^{b^p}=a^k$, $g^p{b}^{-p}=a^m\in ⟨H,S⟩$ and so $a\in ⟨H,S⟩$. ), vertex transitive and edge transitive.

Claim: $\Gamma$ is a non-Cayley. Let $\alpha$ be a vertex corresponding to $H$, namely $G_{\alpha }=H$. Then $G_{\alpha }$ has two orbits on $\Gamma (\alpha )=\{Hgh|h\in H\}\cup \{H{g}^{-1}h:h\in H\}=\Delta \cup {\Delta }^{\prime }$. Notice that $\Gamma (\alpha )=2p$. Assume that there exists a subgroup $R$ of $Aut(\Gamma )$ such that $R$ acts regularly on the vertex set $[G:G_{\alpha }]$. Then $R=C_q:C_p$ by Sylow’s theorem and $p^2|q-1$. Let $X\le Aut(\Gamma )$ such that $X\ge ⟨G,R⟩$. Then $X=R{X}_{\alpha }$ and $X_{\alpha }^{\Gamma (\alpha )}\le \mathrm{Sym}(2p)$. So $q$ does not divide $|X_{\alpha }^{\Gamma (\alpha )}|$ and it follows that $q$ does not divide $|X_{\alpha }|$, due to $\Gamma$ is connected. Thus $⟨a⟩$ is a Sylow $q$-subgroup of $X$ since $q^2$ does not divide $|X|$. By Sylow’s theorems, we may assume $⟨a⟩<R$.(Conjugate some Sylow $q$-subgroup of $X$ to $⟨a⟩$)

Let $Y=N_X(⟨a⟩)$. Then $G$ and $R$ are contained in $Y$. Let $R=⟨a⟩:⟨c⟩$. Then $Z:=⟨a⟩:(⟨b,c⟩)=(⟨a⟩:⟨b⟩)\times C$ where $C=C_X(⟨a⟩{)}_p\cong C_p$, because $|b|=p^2,|c|=p$ and $p^3\nmid q-1$. $Z$ is a subgroup of $Y$. Thus $Z_{\alpha }=⟨b^p⟩\times C_p=C_p\times C_p$. Consider the action of $Z_{\alpha }$ on $\Gamma (\alpha )$. Let $Z_{\alpha }^{[1]}$ be the kernel of $Z_{\alpha }$ acts on $\Delta$, then $Z_{\alpha }^{[1]}\cong C_p$. Define ${\Delta }_i:=\Delta g^i$. If $Z_{\alpha }^{[1]}$ fixes each vertex in ${\Delta }_1$, then look at $Y_{\alpha }^{[1]}$ acts on ${\Delta }_2$. If $Z_{\alpha }^{[1]}$ is non-trivial(as it is of order $p$, stabilizers are either trivial or the whole group) on ${\Delta }_2$, then the induced subgraph on ${\Delta }_1\cup {\Delta }_2$ is $K_{p,p}$.

Then $Z$ is imprimitive on $V\Gamma$ with a block system $\mathcal{B}$ being the set $C-$ orbits on $V\Gamma$ and $\Gamma ={\Gamma }_C[{\overline{K}}_p]$(called lexicographic product) ($\Gamma =(V,E)$, then ${\Gamma }_C=(\mathcal{B},E{\Gamma }_C)$ where $B_i$ adjacent to $B_j$ iff $\exists v_i\in B_i$ and $v_j\in B_j$ such that $v_i,v_j\in E$, ${\overline{K}}_p$ means there are no edges in each blocks).

Then $Aut(\Gamma )\ge S_p\wr Aut({\Gamma }_C)$. Actually ${\Gamma }_C$ is a cycle of order $q$ and $Aut(\Gamma )=S_p\wr D_{2q}$. Since $Z_q$ is not normal in $S_p$, such a group is does not contains $C_q:C_{p^2}$ and so it is impossible. $■$

Thm. (A.Seress, 2005) determined $pq$ and $pqr$ are whether in $\mathcal{N}\mathcal{C}$ or not, where $p$, $q$ and $r$ are distinct primes.

So next step is to determine the cases of products of four distinct primes. An ambitious conjecture:

Conjecture. For any integer $t$, there exists distinct primes $p_1,\cdots ,p_t$ such that each vertex-transitive graph of order $n=p_1\cdots p_t$ is a circulant. Note that $(n,\varphi (n))=1$. And we may assume $p_1<<p_2<<\cdots <<p_t$.