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\nsim v_2\sim \cdots \sim v_{4k-1}\nsim v_{4k}\sim v_{4k+1}=v_0\nsim 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^{\prime },v^{\prime \sigma }=v$. Now $\{v,v^{\prime }\}$ 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^{e}m$, then the order of ${\sigma }^m$ is $2^e$. So define ${\sigma }^{\prime }={\sigma }^m$ and $|{\sigma }^{\prime }|=2^e$. If $|{\sigma }^{\prime }|=2$, then $\sigma$ interchanges $u,v$ and fixes $\{u,v\}$, which is impossible. Thus $4$ divides $|\sigma |$. $■$

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\mathrm{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\le 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\mathrm{mod}4$.

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 $⟨\sigma ⟩$ on $G\backslash \{1\}$ be ${\Delta }_1,\cdots ,{\Delta }_t$. Then $⟨{\sigma }^2⟩$ splits each ${\Delta }_i$ into ${\Delta }_{i1},{\Delta }_{i2}$.

Let $S={\Delta }_{1{ϵ}_1}\cup \cdots \cup {\Delta }_{t{ϵ}_t}$ where ${ϵ}_i\in \{1,2\}$. Then $S^{\sigma }={\Delta }_{1{ϵ}_1^{\prime }}\cup \cdots \cup {\Delta }_{t{ϵ}_t^{\prime }}$ where ${ϵ}_i\ne {ϵ}_i^{\prime }$. 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:⟨\rho ⟩$. Then $G=V:⟨{\rho }^{16}⟩:=V:⟨{\rho }_0⟩.$ Let $\varphi$ be the field automorphism of ${\mathbb{F}}_{3^4}$ and $X={\mathrm{A\Gamma L}}_1(3^4)={\mathrm{AGL}}_1(3^4):⟨\varphi ⟩=V:(\Gamma L_1(3^4))=V:(⟨\rho ⟩:⟨\varphi ⟩)$, where ${\rho }^{\varphi }={\rho }^3$ and $|\varphi |=4$.

Let $\sigma ={\rho }^5{\varphi }^{-1}\in \mathrm{Aut}(G)$. Then ${\sigma }^2={\rho }^{20}{\varphi }^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}\ne {\rho }_0^i$. If $x=v{\rho }_0^i$, $x^{{\sigma }^4}=v^{-1}({\rho }_0^i{)}^{{\sigma }^4}=v^{-1}{\rho }_0^i\ne v{\rho }_0^i$.

So we can construct undirected self-complementary graph $\mathrm{Cay}(G,S)=:\Gamma$ as above. $■$

(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 $\mathcal{D}=\{H\{g,g^{-1}\}H:g\in G\backslash H\}$. Then $\sigma$ acts on $\mathcal{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 $⟨\sigma ⟩$ on $\mathcal{D}$. Then $|{\Delta }_i|\ge 2$ for each $i$ as $\sigma$ is of order $2$-power. And $⟨{\sigma }^2⟩$ 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^{\prime }={\Delta }_{1{\delta }_1^{\prime }}\cup ...\cup {\Delta }_{t{\delta }_t^{\prime }}$ where ${\delta }_i+{\delta }_{i^{\prime }}=1$. Then $S^{\sigma }=S^{\prime }$, $S\cup S^{\sigma }=G/H$ and $S\cap S^{\prime }=\varnothing$. 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=H{S}^{-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=H{S}^{-1}H$, $(HSH{)}^{\sigma }\cap (HSH)=\varnothing$ 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 $H{S}^{-1}H$, which is impossible. $■$

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 }\ne HgH$ for all $g\in T\backslash H$. You can compute matices to show it.

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 }=K{g}^{-1}K$ yields $(KgK{)}^{{\tau }^{2^e}}=KgK$. And it implies $(H_j{t}_j{H}_j{)}^{\sigma }=H_j{t}_j{H}_j$ for all $j$, which is contradictory to $t_i\notin H_i$ and $(H_i{t}_{i}H{)}^{\sigma }\ne H_i{t}_i{H}_i$. $■$