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

Available as .pdf (1.3 MB).

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 C3, C4, C5 or C6
• 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
* 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.