6.1 Self-complementary graph

[TOC]

Definition of Self-complementary graph

Def. A undirected graph $\Gamma =(V,E)$ is self-complementary if $\Gamma \cong \overline{\Gamma }$. An isomorphism $\sigma :\Gamma \to \overline{\Gamma }$ is called a complementing isomorphism. Additionally, $\sigma \in \mathrm{Sym}(V)$ and ${\sigma }^2\in \mathrm{Aut}\Gamma$.

Order of SC graph

Prop. If $\Gamma$ is self-complementary of order $n$, then $n\equiv 0$ or $1\mathrm{mod}4$. Moreover, if $\Gamma$ is regular, $n\equiv 1\mathrm{mod}4$.

Proof. Compute number of edge and valency of $\Gamma$.

Rmk. In fact, for each $n$ with $n$ congruent to $0$ or $1$ modulo $4$, we can construct a self-complement graph of order $n$.

Prop. (Muzuchuk) If $\Gamma$ is vertex-transitive self-complementary graph of order $n$, then $n_p\equiv 1\mathrm{mod}4$for each $n_p$, where $n$ is the largest power of $p$ which divides $n$.

Construct a SC Cayley graph

Prop. Conversely, if $n$ satisfies $n_p\equiv 1\mathrm{mod}4$, then there exists self-complementary Cayley graphs of order $n$.

Proof. Goal: For any $n$ with $n_p$ congruent to $1$ modulo $4$, construct a Cayley graph.

Let $n=p_1^{e_1}\cdots p_t^{e_t}$, where $p_1,\cdots ,p_t$ are distinct primes. Let $R=P_1\times \cdots \times P_t$ where $P_i=Z_{p_i}^{e_i}$.

Let ${\rho }_i\in \mathrm{Aut}(P_i)$ such that $|{\rho }_i|=4$ and let $\rho =({\rho }_1,\cdots ,{\rho }_t)\in \mathrm{Aut}(R)$. Then $|\rho |=4$ and $\rho$ is semi-regular on $R\backslash \{1\}$. Suppose $\rho$ divides $R\backslash \{0\}$ into orbits ${\Delta }_1,\cdots ,{\Delta }_r$. Let $\tau ={\rho }^2$. Then $\tau$ spilts ${\Delta }_i$ into ${\Delta }_{i1}$ and ${\Delta }_{i2}$. Let $S={\Delta }_{11}\cup \cdots \cup {\Delta }_{r1}$. Then $S\cup S^{\rho }=R\backslash \{0\}$. Then $\Gamma =\mathrm{Cay}(R,S)\cong \mathrm{Cay}(R,S^{\rho })=\overline{\Gamma }$. Since $x^{\tau }=x^{-1}$ for any $x\in R$, $\mathrm{Cay}(R,S)$ is undirected. $■$

Edge-trans & SC graph is Cayley with order prime power

Prop. (Zhang, Hong) Let $\Gamma =(V,E)$ be edge-transitive and self-complementary of order $n$. Then

• $n=p^f$ with $p$ odd prime, $n\equiv 1\mathrm{mod}4$.
• $\Gamma$ is vertex-transitive
• $\mathrm{Aut}(\Gamma )\le {\mathrm{A\Gamma L}}_1(p^f)=Z_p^f:{\mathrm{\Gamma L}}_1(p^f)=(Z_p^f:Z_{p^f-1}):Z_f$.
• $\Gamma =\mathrm{Cay}(Z_p^f,S)$.

Proof. Let $G=⟨\mathrm{Aut}\Gamma ,\sigma ⟩\le \mathrm{Sym}(V)$ where $\sigma$ is a complementing isomorphism. Then $G=\mathrm{Aut}\Gamma :Z_2$ is $2$-homogenus on $V$, i.e. $G$ is transitive on $V^{\{2\}}$.

fact: If a $2$-homogenus group $G$ is not $2$-transitive, then $|G|$ is odd.

Since $|G|$ is even, $G$ is $2$-transitive on $V$. For any $a,b\in V$, take $c\in V\backslash \{a,b\}$ and consider $\varphi \in G$ such that $(a,c{)}^{\varphi }=(c,b)$. Note that ${\varphi }^2\in \mathrm{Aut}\Gamma$ and $a^{{\varphi }^2}=b$, so $\mathrm{Aut}\Gamma ⊲G$ is transitive. Moreover, $\mathrm{Aut}\Gamma$ is not $2$-transitive, otherwise $\Gamma$ is $K_n$. By the classification of $2$-transitive groups, we conclude that $G\le {\mathrm{A\Gamma L}}_1(p^f)$, where $p$ is an odd prime, due to the fact that $G$ has a normal subgroup $\mathrm{Aut}\Gamma$ of index $2$ which is not $2$-transitve. In particular, $|V|=p^f$ and $\Gamma$ is Cayley.

fact: An affine 2-transitive group has a unique minimal normal subgroup, which is elementary abelian and acts regularly (known as an EARNS). From stackexchange.

It seems that Zhang Hong’s method is different from that in class: A result of Burnside [1] shows that a doubly transitive group has a unique minimal normal subgroup that is either elementary abelian or simple. Using the classification of finite simple groups and the results by Cameron [2], Curtis, Kantor, and Seitz [3], we shall show that in our case the simple nonabelian group cannot occur as the minimal normal subgroup. Hence $\mathrm{Aut}\Gamma$ must contain a transitive elementary abelian group and $(\mathrm{Aut}\Gamma {)}_{\alpha }$, can be considered as a subgroup the $\mathrm{GL}(n,p)$ acting on the $n$ dimensional vector space over the finite field with $p$ elements, where $\alpha$ is the zero vector of ${\mathbb{F}}_p^n$.

Then the vertex set $V\Gamma$ can be identified with a vector space $V$ such that $\mathrm{Aut}\Gamma$ contains the additive group of $V$ and so $\Gamma$ is Cayley.

ref: Self-complementary symmetric graphs. Zhang, Hong

Now we construct a Cayley graph of order $p^f$. Let $R=Z_p^f$ which can be seen as ${\mathbb{F}}_{p^f}^{+}$. Note that $R$ has an automorphism $\rho \in {\mathbb{F}}_{p^f}^{\times }$ of order $p^f-1$. Then $⟨{\rho }^2⟩$ divides $F^{+}\backslash \{0\}$ into two orbits $S$ and $T$ where $|S|=|T|=\frac{p^f-1}{2}$. Then $\mathrm{Cay}(G,S)\cong \mathrm{Cay}(G,T)$ and $\rho$ is a complementing isomorphism. As $4|p^f-1$, $S=S^{-1}$ and so $\Gamma$ is undirected. $■$

A question

Question. Let $R$ be a finite group. Assume that $R$ has an automorphism $\sigma$ which is of order $2^e$ such that ${\sigma }^2$ fixes no element of $R\backslash \{1\}$.

• Construct a Cayley graph of $R$ which is self-complementary.
• find such non-abelian group $R$.

Here are some properties about fixed-point-free automorphism.

Prop. Let $R$ be a finite group. Assume that $R$ has an automorphism $\rho$ which is of order $2$ and fixes no element of $R\backslash \{1\}$. Then $R$ is of odd order and $R$ is abelian.

Proof. Since $\rho$ fixes no nontrivial element, $R=\{1,r_1,r_1^{\rho },\cdots ,r_s,r_s^{\rho }\}$ and so $R$ is of odd order.

Define $\phi :R\to R,x\mapsto x^{-1}{x}^{\rho }$. If there exist $x\ne y$ with $\phi (x)=\phi (y)$, then $x^{-1}{x}^{\rho }=y^{-1}{y}^{\rho }$ and $y{x}^{-1}=(y{x}^{-1}{)}^{\rho }$, contradication. As $R$ is a finite group, $\phi$ is a bijection. So each element of $R$ can be written in the form of $x^{-1}{x}^{\rho }$. Note that $(x^{-1}{x}^{\rho }{)}^{\rho }=(x^{-1}{x}^{\rho }{)}^{-1}$. Thus $x^{\rho }=x^{-1}$ for all $x\in R$. Then $h^{-1}{g}^{-1}=(gh{)}^{-1}=g^{-1}{h}^{-1}$ for any $g,h\in R$. Therefore, $R$ is abelian. $■$