Self-Complementary Graphs and Generalisations:
a Comprehensive Reference Manual
Alastair Farrugia

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:

* Bipartite self-complementary graphs, or bipsc-graphs, are those bipartite graphs G which are subgraphs of Km,n and isomorphic to their bipartite complement Km,n - G. This concept is entirely different from that of self-complementary graphs which happen to be bipartite (in fact there is only one such example: P4).

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.



Written on: 31st October, 1999.
Last updated: 29th March, 2003.
Home page: www.AlastairFarrugia.net
This page: www.AlastairFarrugia.net/sc-graph.html