|
[[Image:Self-complementary NZ graph.svg|thumb|
{{legend-line|solid #2878BD|Graph {{mvar|A}}}}
{{legend-line|dashed red|[[Graph complement]] of {{mvar|A}}}}
Graph {{mvar|A}} is [[Graph isomorphism|isomorphic]] to its complement.]]
In the [[mathematical]] field of [[graph theory]], a '''self-complementary graph''' is a [[Graphgraph (discrete mathematics)|graph]] which is [[graph isomorphism|isomorphic]] to its [[graph complement graph|complement]]. The simplest non-trivial self-complementary graphs are the {{nowrap|4-vertex}} [[path graph]] and the {{nowrap|5-vertex}} [[cycle graph]]. There is no known characterization of self-complementary graphs.
==Examples==
Every [[Paley graph]] is self-complementary.<ref name="sachs"/> For example, the 3 thinsp;× thinsp;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
==Properties==
An {{nowrap|{{mvar|n}}-vertex}} self-complementary graph has exactly half numberas ofmany 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 (graph diametertheory)|diameter]] either 2 or 3.<ref name="sachs">{{citation
| last = Sachs | first = Horst | authorlink = Horst Sachs
| mr = 0151953
| title = Über selbstkomplementäre Graphen
| volume = 9
| year = 1962}}.</ref> Since {{math|''n''(''n'' –− 1)}} must be divisible by 4, {{mvar|n}} must be [[Congruencemodular relationarithmetic|congruent]] to 0 or 1 [[Modular arithmetic|mod]]modulo 4; for instance, a {{nowrap|6-vertex}} graph cannot be self-complementary.
==Computational complexity==
| 