6.2 Vertex-transitive self-complementary graph

Basic properties

Let $\Gamma =(V,E)$ be a vertex-transitive and self-complementary graph. Let $\sigma$ be a complementing isomorphism of $\Gamma$ satisfying $|\sigma |=2^e$. Take $G\le \mathrm{Aut}\Gamma$ such that $G^{\sigma }=G$ and ${\sigma }^2\in G$.

Lemma 1. Using the notation above, we have:

• $\sigma$ fixes a unique vertex of $\Gamma$;
• $\sigma g$ is a complementing isomorphism for any $g\in G$;
• if $\Gamma$ is undirected, then ${\sigma }^2$ fixes a unique vertex and $|\sigma |$ is divisible by $4$.

Proof. i) Suppose $\sigma$ fixes $u,v\in V$, then $(u,v{)}^{\sigma }=(u,v)$ is an edge (or non-edge) both in $\Gamma$ and $\overline{\Gamma }$, which is impossible. For any $v\in V\Gamma$, suppose $S=v^{⟨\sigma ⟩}$. Since $S^{\sigma }=S$, $[S{]}_{\Gamma }$ is also an self-complementary graph by lemma 2. Thus $|V[S{]}_{\Gamma }|$ is conjugate to $0$ or $1$ modulo $4$. Since $\Gamma$ is vertex-transitive, $|V|$ is odd. Thus there is a $v_0$ such that $|v_0^{⟨\sigma ⟩}|=4k+1$. If $k\ne 0$, then we have $$ v_0\sim v_1\not\sim v_2\sim\cdots\sim v_{4k-1}\not\sim v_{4k}\sim v_{4k+1}=v_0\not\sim v_1,

where $v_i=v_0^i$. Contradiction. ii) is obvious. iii) By i), $\sigma$ fixes a unique point, which is denoted as $u$. Now assume $\sigma^2$ fixes $u$ and $v$. Then $v^\sigma=v',v'^\sigma=v$. Now $\{v,v'\}$ is fixed by $\sigma$, which is impossible. Therefore, $\sigma$ fixes a unique vertex. Moreover, since $\sigma^2\in\mathrm{Aut}\Gamma$, $|\sigma|$ is even. If $|\sigma|=2^em$, then the order of $\sigma^m$ is $2^e$. So define $\sigma'=\sigma^m$ and $|\sigma'|=2^e$. If $|\sigma'|=2$, then $\sigma$ interchanges $u,v$ and fixes $\{u,v\}$, which is impossible. Thus $4$ divides $|\sigma|$. $\blacksquare$ **Lemma 2.** Let $U\subset V$ such that $U^\sigma =U$. Then $[U]_\Gamma$ is self-complementary graph and $\sigma|_U$ is a self-complementing isomorphism. **Thm.** *(Muzychuk)* If $n=|\Gamma|$, then

n_p\equiv 1\mod 4,

where $\Gamma$ is a undirected vertex-transitive self-complementary graph. **Proof.** Let $P$ be a Sylow $p$-subgroup of $G$. Then $P^\sigma$ is a Sylow $p$-subgroup and there is $x\in G$ such that $(P^{\sigma})^x=P$. Let $\tau=\sigma x$. Then $\tau$ is a complementing isomorphism of $\Gamma$ by lemma 1. Thus $\tau$ fixes a unique vertex, denoted as $\alpha\in V$. Furthermore, $P_\alpha^\tau=P_\alpha$. thus define $U=[P:P_\alpha]$ and $U^\tau=U$. By lemma 2, $[U]_\Gamma$ is self-complementary. Since $P\leq G$ is transitive on $U$, $[U]_\Gamma$ is vertex-transitive self-complementary and so $|U|\equiv 1(4)$. Finially, $n=|G|/|G_\alpha|$ and $n_p=|G|_p/|G_\alpha|_p=|P|/|P_\alpha|=|U|$ yields $n_p\equiv 1\mod4$. ### Construction of SCVT Cayley graph Let $G$ be a group and $\sigma\in\mathrm{Aut}(\Gamma)$ such that $\sigma^2$ fixes no element of $G\backslash\{1\}$. Let the orbit of $\langle\sigma\rangle$ on $G\backslash\{1\}$ be $\Delta_1,\cdots,\Delta_t$. Then $\langle \sigma^2\rang$ splits each $\Delta_i$ into $\Delta_{i1},\Delta_{i2}$. Let $S=\Delta_{1\epsilon_1}\cup\cdots\cup\Delta_{t\epsilon_t}$ where $\epsilon_i\in\{1,2\}$. Then $S^\sigma=\Delta_{1\epsilon_1'}\cup\cdots\cup\Delta_{t\epsilon_t'}$ where $\epsilon_i\neq\epsilon_i'$. Now $\Gamma=\mathrm{Cay}(G,S)$ is self-complementary and undirected, with complementing isomorphism $\sigma$. **Exm.** Let $G=3^4:5$ be a Frobenius group. $G<\mathrm{AGL}_1(3^4)=3^4:Z_{80}=V:\lang \rho\rang$. Then $G=V:\lang \rho^{16}\rang:=V:\lang \rho_0\rang.$ Let $\phi$ be the field automorphism of $\mathbb F_{3^4}$ and $X=\mathrm{A\Gamma L}_1(3^4)=\mathrm{AGL}_1(3^4):\lang\phi\rang=V:(\Gamma L_1(3^4))=V:(\lang\rho\rang:\lang\phi\rang)$, where $\rho^\phi=\rho^3$ and $|\phi|=4$. Let $\sigma=\rho^5\phi^{-1}\in\mathrm{Aut}(G)$. Then $\sigma^2=\rho^{20}\phi^2$, $\sigma^4=\rho^{40}$. Thus $|\sigma|=8$. Claim: $\sigma^2$ is fixed-point free on $G\backslash\{1\}$. An element of $G$ have the form $x=v\rho_0^i$. If $x=\rho_0^i$, $x^{\sigma^2}=\rho_0^{i\cdot 9}\neq \rho_0^i$. If $x=v\rho_0^i$, $x^{\sigma^4}=v^{-1}(\rho_0^i)^{\sigma^4}=v^{-1}\rho_0^i\neq v\rho_0^i$. So we can construct undirected self-complementary graph $\mathrm{Cay}(G,S)=:\Gamma$ as above. $\blacksquare$ **(research) Problem.** Explicitly construct finite groups which have fixed-point free automorphism of order $2^e>2$. ### Construction of SCVT Coset graph **Thm.** Let $G$ be a group and $H<G$ be core-free. Then there exists an undirected self-complementary graph $\Gamma=\mathrm{Cos}(G,H,HSH)$ with a complementing isomorphism in $\mathrm{Aut}(G,H)$ iff there exists $\sigma\in\mathrm{Aut}(G,H)$ of order $2$-power s.t. $\sigma$ fixes no $H\{g,g^{-1}\}H$. **Proof.** Assume $\sigma$ fixes no $H\{g,g^{-1}\}H$. Let $\mathscr D=\{H\{g,g^{-1}\}H:g\in G\backslash H\}$. Then $\sigma$ acts on $\mathscr D$ by $(H\{g,g^{-1}\}H)^\sigma=H\{g^{\sigma},(g^{\sigma})^{-1}\}H$. Let $\Delta_1,\cdots,\Delta_t$ be the orbits of $\lang\sigma\rang$ on $\mathscr D$. Then $|\Delta_i|\geq 2$ for each $i$ as $\sigma$ is of order $2$-power. And $\lang\sigma^2\rang$ divides $\sigma_i$ into $\Delta_{i0}$ and $\Delta_{i1}$. Clearly, $\sigma$ interchanges $\Delta_{i0}$ and $\Delta_{i1}$. Let $S=\Delta_{1\delta_1}\cup...\cup\Delta_{t\delta_t}$ and $S'=\Delta_{1\delta_1'}\cup...\cup\Delta_{t\delta_t'}$ where $\delta_{i}+\delta_{i'}=1$. Then $S^{\sigma}=S'$, $S\cup S^\sigma=G/H$ and $S\cap S'=\empty$. Thus $\mathrm{Cos}(G,H,S)$ is self-complementing graph, where $S=H\{g_1,g_1^{-1}\}H\cup\cdots\cup H\{g_t,g_t^{-1}\}H$ for some $g_i\in G\backslash H$. As $HSH=HS^{-1}H$, $\Gamma$ is undirected. Conversely, if $\Gamma=\mathrm{Cos}(G,H,HSH)$ is undirected self-complementary graph with a complementing isomorphism $\sigma\in \mathrm{Aut}(G,H)$, then $HSH=HS^{-1}H$, $(HSH)^\sigma\cap(HSH)=\empty$ and $(HSH)^\sigma\cup HSH=G\backslash H$. If there is a $g\in G\backslash H$ satisfying $(H\{g,g^{-1}\}H)^\sigma=H\{g,g^{-1}\}H$, then $H\{g,g^{-1}\}H$ has non-empty intersection with $HSH$ and $HS^{-1}H$, which is impossible. $\blacksquare$ #### Example 1. For $H<G$, there is $\mathrm{Cos}(G,H,HSH)$ which is self-complentary if there exists $\sigma\in\mathrm{Aut}(G,H)$ such that $\sigma^2$ fixes no $HgH$ for any $g\in G\backslash H$. Since $\sigma^2$ fixes no $HgH$, we have $\sigma$ fixes no $H\{g,g^{-1}\}H$. By the previous theorem, $\Gamma$ is undirected SC graph. #### Example 2. Let $T=\mathrm{PSL}_2(q^2)$ with $q$ odd prime and $H=D_{q^2-1}<_{\max} T$. We want to find a $S$ such that $\mathrm{Cos}(T,H,HSH)$ is self-complentary. **Thm.** Let $T=\mathrm{PSL}_2(q^2)$ with $q$ odd, and let $H=D_{q^2-1}$. Let $\sigma=\delta\psi$ where $\delta$ is a diagonal automorphism of $T$ and $\psi$ is a field automorphism of order $2$. Then there exists a SC graph $\Gamma=\mathrm{Cos}(T,H,HSH)$ with $\sigma$ being a complementing isomorphism of $\Gamma$ and $\Gamma$ is not undirected. **Proof.** Show $(HgH)^\sigma\neq HgH$ for all $g\in T\backslash H$. You can compute matices to show it. ![[Pasted image 20240430191318.png]] **Exm.** *(BLOW UP)* Given $T,H,\sigma$ as above, let $G=T_1\times\cdots\times T_{2^e}=T^{2^e}$. Define $\pi:(t_1,\cdots,t_{2^e})\to(t_{2^e},t_1,\cdots,t_{2^e-1})$, $\pi\in\mathrm{Aut}(G)$. Let $H_i<T_i$ such that $H_i\cong H=D_{q^2-1}$ and $H_i^\pi=H_{i+1}$. Let $K=H_1\times\cdots\times H_{2^e}<G$ and $\tau=(\sigma,1,\cdots,1)\pi^{-1}$. Then $\tau\in\mathrm{Aut}(G,K)$. Claim: $\tau$ does not fix $K\{g,g^{-1}\}K$ for any $g\in G\backslash K$. Suppose $(K\{g,g^{-1}\}K)^\tau=K\{g,g^{-1}\}K$. Then as $g=(t_1,\cdots,t_{2^e})\notin K$, $t_i\notin H_i$ for some $i$ and $K=H_1\times\cdots\times H_{2^e}$. Note that $\tau^{2^e}=(\sigma,\cdots,\sigma)$. Whether $(KgK)^\tau=KgK$ or $(KgK)^\tau=Kg^{-1}K$ yields $(KgK)^{\tau^{2^e}}=KgK$. And it implies $(H_jt_jH_j)^{\sigma}=H_jt_jH_j$ for all $j$, which is contradictory to $t_i\notin H_i$ and $(H_it_iH)^\sigma\neq H_it_iH_i$. $\blacksquare$