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:

• any sc-graph G on n >= 4 vertices is contained in a sc-graph G' on n+4 vertices with diameter 3 but no end-vertices (this was already known for the other two possibilities, namely when G' has end-vertices or diameter 2)
• known results imply a partial generalisation of Turán's theorem, namely that every graph on n >= 6 vertices with m >= n(n-1)/4 edges must contain C₃, C₄, C₅ or C₆
• certain difficulties in a construction of Nair and Vijayakumar were resolved after some correspondence with these two authors
• a graph found by Hartsfield was used to construct an infinite family of sc-graphs whose antimorphisms have unequal cycle lengths
• disconnected bipsc-graphs^* with isolated vertices are characterised
• there is a simpler proof of a result by Gangopadhyay and Rao Hebbare on the diameter of connected bipsc-graphs^*, as well as a result on the radius of these graphs

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.