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 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 or 529-Peisert graph.
See also
Graph Complement, Isomorphic Graphs
Explore with Wolfram|Alpha
References
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.
https://alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Harary,
F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems."
In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam,
Netherlands: North-Holland, pp. 259-275, 1973.House of Graphs.
9-Vertex Self-Complementary Graphs. 1,
2, 3,
4, 5,
and others.Peisert, W. "All Self-Complementary Symmetric Graphs."
J. Algebra 240, 209-229, 2001.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.
Royle, G. "Self-Complementary
Graphs." http://school.maths.uwa.edu.au/~gordon/remote/selfcomp/Sachs,
H. "Über selbstkomplementäre Graphen." Publ. Math. Debrecen 9,
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. B 25, 143-150, 1978.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Self-Complementary Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Self-ComplementaryGraph.html