Selfcomplementary graphs |

Two
labelled graphs *f, [~f] Î2 ^{ [v choose 2]}*
are called

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

(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

| (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

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 onvvertices is equal towhere(1)/(v!)å_{p}'2^{c( bar ( p)) }= å_{a}'(2^{c bar (a) })/(Õ_{i}i^{ai}a_{i}!),cis as in Corollary, and where_{ bar (a)}å'denotes the sum over all the cycle types_{a}asuch that for each elementpwith this cycle type, the correspondingbar ( 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 onvvertices exist if and only ifvis 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

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Selfcomplementary graphs |