[TOC]
Definition of Self-complementary graph
Def. A undirected graph is self-complementary if . An isomorphism is called a complementing isomorphism. Additionally, and .
Order of SC graph
Prop. If is self-complementary of order , then or . Moreover, if is regular, .
Proof. Compute number of edge and valency of .
Rmk. In fact, for each with congruent to or modulo , we can construct a self-complement graph of order .
Prop. (Muzuchuk) If is vertex-transitive self-complementary graph of order , then $$ n_p\equiv 1\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\mod4$, 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. $\blacksquare$ ### 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\mod 4$. - $\Gamma$ is vertex-transitive - $\mathrm{Aut}(\Gamma)\leq\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=\langle\mathrm{Aut}\Gamma,\sigma\rangle\leq\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 $\phi\in G$ such that $(a,c)^\phi=(c,b)$. Note that $\phi^2\in \mathrm{Aut}\Gamma$ and $a^{\phi^2}=b$, so $\mathrm{Aut}\Gamma\lhd 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\leq\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](https://articles-w4dgmmgjg5hymaap5dw3gbg7.must.wf/book/1558742/bb4cef) 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 $\langle\rho^2\rangle$ 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. $\blacksquare$ ### 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$. [comment]:<> (我猜这是个open-question，所以先摆在这好了。) 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 $\varphi:R\to R,x\mapsto x^{-1}x^\rho$. If there exist $x\neq y$ with $\varphi(x)=\varphi(y)$, then $x^{-1}x^\rho=y^{-1}y^\rho$ and $yx^{-1}=(yx^{-1})^\rho$, contradication. As $R$ is a finite group, $\varphi$ 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. $\blacksquare$