In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a self-complementary graph is a
graph which is
isomorphic to its
complement. The simplest non-trivial self-complementary graphs are the
path graph and the
cycle graph. There is no known characterization of self-complementary graphs.
Examples
Every
Paley graph is self-complementary.
For example, the 3 × 3
rook's graph (the Paley graph of order nine) is self-complementary, by a symmetry that keeps the center vertex in place but exchanges the roles of the four side midpoints and four corners of the grid. All
strongly regular self-complementary graphs with fewer than 37 vertices are Paley graphs; however, there are strongly regular graphs on 37, 41, and 49 vertices that are not Paley graphs.
The
Rado graph is an infinite self-complementary graph.
Properties
An self-complementary graph has exactly half as many edges of the
complete graph, i.e., edges, and (if there is more than one vertex) it must have
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
either 2 or 3.
[.] Since must be divisible by 4, must be
congruent to 0 or 1 modulo 4; for instance, a graph cannot be self-complementary.
Computational complexity
The problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are
polynomial-time equivalent to the general
graph isomorphism problem.
[.]
References
External links
*{{mathworld, id=Self-ComplementaryGraph, title=Self-Complementary Graph, mode=cs2
Graph families