# 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 .

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 , 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 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 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, and implying that Aut(X) is imprimitive by Theorem 1.9. Suppose the blocks have length d and . By Lemma 1.8 we know that the blocks have the form , . Since Xc has the same automorphism group as X, are also the blocks of length d for the group acting on V(Xc). Thus, any isomorphism of X to Xc must act as a permutation on the set of blocks. The action of tells us that the subgraphs induced by X on , respectively, are all isomorphic to each other. Further, the action of implies that are all circulant graphs. We conclude that X0itself is a self-complementary circulant graph.

The permutation cyclically permutes the blocks so that the action of on the blocks contains the regular representation of the cyclic group of order n/d. If 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 are maximal non-trivial blocks of Aut(X), that is, the only block properly containing B0 is all of V(X).

Since X is a minimal counter-example, the self-complementary circulant subgraph X0 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 is either doubly transitive or imprimitive. It cannot be imprimitive as this would allow us to find a non-trivial block properly containing B0. Hence, 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 d2 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 Xc are different. Thus, X cannot be self-complementary. The necessity now follows.

Brian &
2000-01-24