All graphs in this paper have neither loops nor multiple edges. We use
V(X) and E(X) to denote the vertex set and edge set of X, respectively.
Given a graph X, the complement of X, denoted Xc, satisfies uis adjacent to v in X if and only if u is not adjacent to v in
A graph X is said to be self-complementary if it is isomorphic
to its complement.
The following proposition is simple to prove so we omit its proof.
is a self-complementary regular graph, we have
such that if and only if
H. Sachs  showed how to construct self-complementary circulant
graphs of order n whenever n is a product of primes all of which are
congruent to 1 modulo 4. He further wrote that there are reasons to
conjecture that it is necessary that all
the primes in the prime factorization of n be congruent to 1 modulo 4.
He supported this statement by demonstrating the non-existence of
self-complementary circulant graphs of orders n=p2e, n=pq and
n=9r, where p and q are any primes congruent to 3 modulo 4, and
r>5 is a prime congruent to 1 modulo 4.
circulant graph X
) of order n is the graph whose vertex set
with an edge joining ui and uj if and
only if , where the latter computation is done modulo n. The set
S is called the
connection set of the circulant.
D. Froncek, A. Rosa and J. Siran  have proved that
is true, that is, they showed that there exists a self-complementary
circulant graph of order n if and only if every prime in the prime
factorization of n is congruent to 1 modulo 4. Their proof is graph
theoretic. In this paper, we provide a simple algebraic proof. First,
some preliminary results about permutation groups are required.
Let G be a permutation group acting on . If
has the property that for every , either
, then B is called a
It is easy to see that ,
and any singleton are blocks
of any permutation group. They are called trivial blocks for this reason.
All other blocks are called non-trivial.
Let G be a transitive permutation group. If G has any non-trivial
blocks, then G is said to be an imprimitive group. Otherwise, Gis said to be primitive.
Note that if G is imprimitive, then given a non-trivial block B,
there is a partition of
obtained by taking B and all its
images under the action of G. This is called a complete block
system and all the blocks have the same cardinality; the latter is
frequently called the length of a block.
Let G be an abstract finite group. If every primitive group containing
the regular representation of G as a transitive subgroup is doubly
transitive, then G is said to be a Burnside group.
Burnside groups are nice groups for graph theory. Why? If we form
any Cayley graph on a Burnside group G, then the regular representation of
G is contained in the automorphism group of the graph as a transitive
subgroup. Hence, if the Cayley graph is neither complete nor the complement
of the complete graph, then the automorphism group must act imprimitively
on the vertex set of the graph. This is especially nice for circulant graphs
because of the following result telling us precisely what the blocks are.
PROOF.Let B be a block of length d.
Taking all the blocks belonging to the complete block system containing
B, we see that this partitions the vertex set into parts all of which
have d elements. Thus, d is a divisor of n.
is not prime and the automorphism group
)of a circulant graph
of order n
acts imprimitively on the vertex set of X
with blocks of
, then d
is a divisor of n
and the blocks are the sets
We know that the permutation
the definition of blocks and from the action of ,
it is easy to see
that each block must be made up of vertices equally spaced n/d apart in
the order in which they occur in .
This completes the proof.
The following two known results are required later. The simple proof
of the second is omitted.
The cyclic groups of composite order all are Burnside groups.
be an imprimitive group with blocks
denote the action of G
on the set of blocks. If
is itself imprimitive with blocks
is imprimitive with blocks
is the union of the blocks comprising Ci