Self-Complementary Graph

A self-complementary graph is a graph which is isomorphic to its graph complement. The numbers of simple self-complementary graphs on , 2, ... nodes are 1, 0, 0, 1, 2, 0, 0, 10, ... (OEIS A000171). The first few of these correspond to the singleton graph, the path graph , and the cycle graph .

Every self-complementary graph is not only connected, but also traceable (Clapham 1974, Camion 1975; Farrugia 1999, p. 52). Furthermore, all nontrivial self-complementary graphs have graph diameter 2 or 3 (Sachs 1962; Skiena 1990, p. 187). For a self-complementary graph on vertices, there is a graph cycle of length for every integer (Rao 1977; Farrugia 1999, p. 51). As a result, the graph circumference of a self-complementary graph on vertices is either (i.e., the graph is Hamiltonian), , or (Farrugia 1999, p. 51).

By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., edges for a self-complementary graph on vertices. Since must be divisible by 4, it follows that or 1 (mod 4).

There is a polynomial-time condition to determine if a self-complementary graph is Hamiltonian.

The number of self-complementary graphs on nodes can be obtained from the Polya polynomial derived from Pólya's enumeration theorem used to enumerate the numbers of simple graphs as . Harary and Palmer (1973, p. 260) list the enumeration of labeled self-complementary graphs as a graphical enumeration problem.

All self-complementary symmetric graphs were identified by Peisert (2001). Peisert (2001) observed that graphs which are both symmetric and self-complementary are necessarily strongly regular, arc-transitive, and distance-transitive, and proved that they are given by the Paley graphs, Peisert graphs, and one exceptional graph on 529 vertices that is not isomorphic to either the 529-Paley graph or 529-Peisert graph.