A self-complementary graph is a simple graph that is isomorphic to its graph
complement. The graphs considered here are finite
and have positive graph order. The numbers of nonisomorphic
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 nonisomorphic 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 nontrivial self-complementary symmetric graphs were identified by Peisert (2001). Peisert (2001) observed that these graphs 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.
The only bipartite self-complementary graphs of positive graph order are the singleton
graph 
and the path graph 
. To see this, let 
be such a graph and choose proper
colorings of 
and its graph complement,
each with at most two colors. No two vertices can
receive the same pair of colors, since they would be nonadjacent in both 
and its graph complement.
Thus 
has at most four vertices. The edge
count restriction leaves only orders 1 and 4,
and the unique self-complementary graph of graph
order 4 is 
.
Consequently, a grid graph formed as a graph Cartesian product of finitely many path graphs
with positive orders is self-complementary iff
all factors are singleton graphs, or exactly one
factor is the path graph 
and all others are singleton
graphs.
