Available as .pdf (1.3 MB).
Updates
and Correspondence
Detailed
Contents
Acknowledgements
Overview (top)
A graph which is isomorphic to its complement is
said to be a self-complementary graph, or sc-graph for short. These graphs
have a high degree of structure, and yet they are far from trivial. Suffice
to say that the problem of recognising self-complementary graphs, and the
problem of checking two sc-graphs for isomorphism, are both equivalent
to the graph isomorphism problem.
My M.Sc. Thesis (University of Malta, August 1999) takes a look at this and several other results discovered by the hundreds of mathematicians who studied self-complementary graphs in the four decades since the seminal papers of Sachs (Über selbstkomplementäre graphen, Publ. Math. Drecen 9 (1962) 270--288. MR 27:1934), Ringel (Selbstkomplementäre Graphen, Arch. Math. 14 (1963) 354--358. MR 25:22) and Read (On the number of self-complementary graphs and digraphs, J. Lond. Math. Soc. 38 (1963) 99--104. MR 26:4339).
It is a manual more than a survey, as it contains all the results I could find, and quite a few proofs. There are also a few original results:
Layout of the Manual (top)
Chapter 1 describes the fundamental structural properties of sc-graphs
and their antimorphisms; it also contains several miscellaneous results
which do not warrant a chapter to themselves.
Chapter 2 covers results on paths, circuits and cliques in self-complementary
graphs, while Chapter 3 is about regular sc-graphs and the very strong
properties they enjoy (or suffer from).
Chapter 4 discusses the problem of generating self-complementary graphs, and distinguishing them from each other and from non-self-complementary graphs. It also shows how sc-graphs have been either used as tools, or investigated in their own right, in such areas as the isomorphism problem, the reconstruction conjecture, codes and information. Chapter 5 describes several related concepts such as multipartite self-complementary graphs and almost self-complementary graphs.
The final two chapters are meant as a useful reference guide to results on degree sequences and enumeration of sc-graphs. Virtually no proofs are presented in these two chapters, but the enumeration results are useful even to those not particularly interested in enumeration, because they show that many self-complementary structures described in Chapter 5 are linked not only by an intuitive resemblance, but also by very similar counting formulas.