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.