{{short description|Graph which is isomorphic to its complement}} thumb|class=skin-invert-image| {{legend-line|solid #2878BD|Graph {{mvar|A}}}} {{legend-line|dashed red|Graph complement of {{mvar|A}}}} Graph {{mvar|A}} is isomorphic to its complement.
In the mathematical field of graph theory, a '''self-complementary graph''' is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the {{nowrap|4-vertex}} path graph and the {{nowrap|5-vertex}} cycle graph.
==Examples== Every Paley graph is self-complementary.<ref name="sachs"/> 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.<ref>{{citation | last = Shpectorov | first = S. | doi = 10.1016/S0012-365X(98)0007X-1 | issue = 1–3 | journal = Discrete Mathematics | mr = 1656740 | pages = 323–331 | title = Complementary ''l''<sub>1</sub>-graphs | volume = 192 | year = 1998| url = https://research.birmingham.ac.uk/en/publications/13d88507-fdb4-4d71-9456-a44faaee8258 | doi-access = }}.</ref> 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.<ref>{{citation | last = Rosenberg | first = I. G. | contribution = Regular and strongly regular selfcomplementary graphs | mr = 806985 | location = Amsterdam | pages = 223–238 | publisher = North-Holland | series = North-Holland Math. Stud. | title = Theory and practice of combinatorics | volume = 60 | year = 1982}}.</ref>
The Rado graph is an infinite self-complementary graph.<ref>{{citation | last = Cameron | first = Peter J. | authorlink = Peter Cameron (mathematician) | contribution = The random graph | mr = 1425227 | location = Berlin | pages = 333–351 | publisher = Springer | series = Algorithms Combin. | title = The mathematics of Paul Erdős, II | volume = 14 | arxiv = 1301.7544 | year = 1997| bibcode = 2013arXiv1301.7544C }}. See in particular Proposition 5.</ref>
==Properties== An {{nowrap|{{mvar|n}}-vertex}} self-complementary graph has exactly half as many edges of the complete graph, i.e., {{math|''n''(''n'' − 1)/4}} edges, and (if there is more than one vertex) it must have diameter either 2 or 3.<ref name="sachs">{{citation | last = Sachs | first = Horst | authorlink = Horst Sachs | mr = 0151953 | journal = Publicationes Mathematicae Debrecen | pages = 270–288 | title = Über selbstkomplementäre Graphen | volume = 9 | year = 1962 | issue = 3–4 | doi = 10.5486/PMD.1962.9.3-4.11 }}.</ref> Since {{math|''n''(''n'' − 1)}} must be divisible by 4, {{mvar|n}} must be congruent to 0 or 1 modulo 4; for instance, a {{nowrap|6-vertex}} 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.<ref>{{citation|last1=Colbourn|first1=Marlene J.|last2=Colbourn|first2=Charles J.|author2-link=Charles Colbourn|title=Graph isomorphism and self-complementary graphs|journal=SIGACT News|year=1978|volume=10|issue=1|pages=25–29|doi=10.1145/1008605.1008608}}.</ref>
==References== {{reflist}}
==External links== *{{mathworld|id=Self-ComplementaryGraph|title=Self-Complementary Graph|mode=cs2}}
Category:Graph families