Main Result

We are now ready to prove the main result whose statement follows.

Theorem 2.1   There exists a self-complementary circulant graph with n vertices if and only if every prime p in the prime factorization of n satisfies $p\equiv 1(\mathrm{mod}\;4)$.

PROOF.For the sake of completeness and because of its brevity, we give a proof of the sufficiency in spite of the fact Sachs [2] also did it. When $p\equiv 1\mbox{(mod }4)$, it is easy to see that the circulant graph X(p;S), where S is the set of quadratic residues modulo p, is self-complementary. If X is a self-complementary circulant graph of order m, then the wreath product $X(p;S)\wr X$ is easily seen to be self-complementary of order pm. Thus, there is a self-complementary circulant graph of order n whenever all the primes in the prime factorization of n are congruent to 1 modulo 4.

We prove necessity by induction on n. Let X be a self-complementary circulant graph of smallest order which is a counter-example. We know that $n\equiv 1\mbox{(mod }4)$ is satisfied. Hence, n is composite and has 2r, r>0, primes congruent to 3 modulo 4 in its prime factorization.

Since n is composite and X is self-complementary, $X\neq K_n$ and $X\neq K_n^c$ implying that Aut(X) is imprimitive by Theorem 1.9. Suppose the blocks have length d and $\rho=(u_0\;u_1\;\cdots\;u_{n-1})$. By Lemma 1.8 we know that the blocks have the form $B_i=\{u_j:j\equiv i\mbox{ (mod n/d)}\}$, $i=0,1,\ldots,n/d-1$. Since X^c has the same automorphism group as X, $B_0,B_1,\ldots,B_{n/d-1}$ are also the blocks of length d for the group acting on V(X^c). Thus, any isomorphism of X to X^c must act as a permutation on the set of blocks. The action of $\rho$ tells us that the subgraphs $X_0,X_1,\ldots,X_{n/d-1}$ induced by X on $B_0,B_1,\ldots,B_{n/d-1}$, respectively, are all isomorphic to each other. Further, the action of $\rho^{n/d-1}$ implies that $X_0,X_1,\ldots,X_{n/d-1}$ are all circulant graphs. We conclude that X₀itself is a self-complementary circulant graph.

The permutation $\rho$ cyclically permutes the blocks so that the action of $\overline{\mbox{Aut}(X)}$ on the blocks contains the regular representation of the cyclic group of order n/d. If $\overline{\mbox{Aut}(X)}$ is imprimitive, then we can find a block system for Aut(X) acting on V(X) with blocks of length d', where d'>d, by Proposition 1.10. Without loss of generality, we may assume that $B_0,B_1,\ldots,B_{n/d-1}$ are maximal non-trivial blocks of Aut(X), that is, the only block properly containing B₀ is all of V(X).

Since X is a minimal counter-example, the self-complementary circulant subgraph X₀ cannot be a counter-example. Thus, the prime factorization of d has no primes congruent to 3 modulo 4. However, n has at least two primes congruent to 3 modulo 4 in its prime factorization. Thus, n/d is composite and $\overline{\mbox{Aut}(X)}$ is either doubly transitive or imprimitive. It cannot be imprimitive as this would allow us to find a non-trivial block properly containing B₀. Hence, $\overline{\mbox{Aut}(X)}$acts doubly transitively on the set of blocks. This implies that the number of edges between any two blocks is the same. However, there are d² possible edges between any two blocks which is odd because d is odd. This means that the parities of the numbers of edges between any two blocks in X and X^c are different. Thus, X cannot be self-complementary. The necessity now follows.