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 trivial graph on one node, 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 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
(Furrigia 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 "graph polynomial"
derived form Pólya's enumeration theorem used to enumerate the numbers of
simple graphs as .
Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la théorie des graphes (Paris, 1974)
(Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre Études
de Recherche Opér. (Bruxelles)17, pp. 173-183, 1975.Clapham,
C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc.
Math.8, 251-255, 1974.Farrugia, A. "Self-Complementary
Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999.
http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Rao,
S. B. "Cycles in Self-Complementary Graphs." J. Combin. Th.
|bf 22, 1-9, 1977.Read, R. C. "On the Number of Self-Complementary
Graphs and Digraphs." J. London Math. Soc.38, 99-104, 1963.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Sachs,
H. "Über selbstkomplementäre Graphen." Publ. Math. Debrecen9,
270-288, 1962.Skiena, S. "Self-Complementary Graphs." §5.2.3
in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 187, 1990.Sloane, N. J. A. Sequence
A000171/M0014 in "The On-Line Encyclopedia
of Integer Sequences."Wille, D. "Enumeration of Self-Complementary
Structures." J. Combin. Th. B25, 143-150, 1978.
, 2, ... nodes are 1, 0, 0, 1, 2, 0, 0, 10, ... (OEIS A000171). The first few of these correspond to
the trivial graph on one node, the path graph 
,
and the cycle graph 
.
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 
(Furrigia 1999, p. 51).
edges for a self-complementary graph on 
vertices. Since 
must be divisible by 4, it follows that 
or 1 (mod 4).
nodes can be obtained from the "graph polynomial"
derived form Pólya's enumeration theorem used to enumerate the numbers of
simple graphs as 
.
