Self-complementary graphs and generalisations : a comprehensive reference manual

Abstract

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 the equivalent to the graph isomorphism problem. We take 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 (Uber selbstkomplementare graph, Publ. Nfa.tll. Drecen 9 (1962) 270-288. MR 27:1934), Ringel (Selbstkomplementare Graph, Arch. Nfatl1. 14 (1963) 354-358. MR 25:22) and Read (On the number of self-complementary graphs and digraphs, J. Land. Nfatli. Soc. 38 (1963) 99-104. MR 26:4339). The areas covered include distance, connectivity, eigenvalues, and colouring problems in Chapter 1; circuits (especially triangles and Hamiltonicity) and Ramsey numbers in Chapter 2; regular self-complementary graphs and Kotzig's conjectures in Chapter 3; the isomorphism problem, the reconstruction conjecture and self-complement indexes in Chapter 4; self complementary and self-converse digraphs, multi-partite sc-graphs and almost sc-graphs in Chapter 5; degree sequences in Chapter 6, and enumeration in Chapter 7. The thesis is intended to be as comprehensive as possible, and there are also a few original results. I intend to update this survey every now and then, and to publish it on the internet.