### Selfcomplementary graphs

Two
labelled graphs *f, [~f] Î2*^{ [v choose 2]}
are called *complementary*
if and only if
* [~f] ( {i,j })=0 iff f( {i,j })=1. *

Two complementary labelled graphs

Correspondingly we say that two graphs, i.e. isomorphism
classes of labelled
ones, are *complementary*
graphs if and only if one class arises
from the other by
forming the complements. The example of figure
shows that graphs may very well
be *selfcomplementary* , and hence we ask for the number
of selfcomplementary graphs on *v* vertices.
In order to prepare the derivation of this number, we notice that the classes
which we obtain by putting a graph and its complement together in one class
are just the orbits of the group *H ´G :=S*_{2} ´S_{ v} on
the set *Y*^{X}:=2^{ [v choose 2]}(recall the section of paragigmatic examples).
According to Theorem
the number of these orbits is equal to

**(**1**)/(**2 ·v!**)** å_{( r, p) ÎS2
´S v}
Õ_{i=1}^{[v choose 2]} | 2_{ ri} | ^{ai( bar ( p))}.

But * | 2*_{ ri} | , the number of fixed points of * r*^{i}, rÎS_{2}, acting on the set *2*,
is either 2 or zero. Hence
we separate
the sum over the *( r, p) ÎS*_{2} ´S_{ v}
into two sums depending on * rÎS*_{2} and get the following
expression for the number of these orbits:
*
| (S*_{2} ´S_{ v}) \\2^{ [v choose 2]}
| =**(**1**)/(**2 ·v!**)** ( å_{p}2^{c( bar ( p))}+ å_{p}'
2^{c( bar ( p))} ),

where * å*_{p} means the sum over all the elements of * S*_{v} , while
* å'*_{p} means the sum over all the elements * p* of * S*_{v} such that
* bar ( p)* does not contain a cycle of odd length, i.e.
*a*_{2i+1}( bar ( p))=0, for each *i*.
There is a program to compute the
number of orbits, which consist of graphs and their
complements.
In order to derive from this equation
the total number of selfcomplementary graphs on *v*
vertices we use an easy argument which
we have already met when we introduced the
notions of enantiomeric pairs and selfenantiomeric orbits.
A group of order 2 consisting of the identity map and the
''complementation `` acts on the set
of graphs.
This action is chiral if *v >= 2*, and
hence the desired number of selfcomplementary graphs is
twice the number given in examples minus the number in
Corollary.
We have obtained

**Corollary: **
* The number of selfcomplementary
graphs on **v* vertices
is equal to
**(**1**)/(**v!**)** å_{p}'2^{c( bar ( p))
} = å_{a}'**(**2^{c bar (a)
}**)/(** Õ_{i}i^{ai}a_{i}!**)** ,

where *c*_{ bar (a)} is as in Corollary, and where * å'*_{a} denotes the sum
over all the cycle types *a* such that for each element * p* with this
cycle type, the corresponding * bar ( p)* does not contain any cycle of
odd length.

There are some numerical results for
the number of selfcomplementary graphs.
This leads to an existence
theorem (cf. exercise):

**Theorem: **
*
Selfcomplementary graphs
on **v* vertices exist if and only if *v*
is congruent to 0 or 1 modulo 4.

Proof:
By corollary a selfcomplementary graph exists if and only if
there are * pÎS*_{ v} such that * bar ( p)* does not
contain any cycle of odd length. Now, if neither *v º0 (4)* nor
*v º1 (4)*, then *[v choose 2]* is
odd so that each * bar ( p), pÎS*_{ v}, must
contain a cyclic factor
of odd length. On the other hand,
if *v º0 (4)*, then to the full cycle * p:=(1 ...v) ÎS*_{ v} there corresponds a permutation * bar ( p)* which, by
lemma,
does not contain a cyclic factor of odd length. Finally,
in the case when *v º1
(4)*, we consider * p:=(1 ...v-1)(v)*. Again by
lemma, * bar ( p)*
does not contain any cyclic factor of odd length.

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001