self-complementary graph
{{short description|Graph which is isomorphic to its complement}}
[[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 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. 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.{{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 l1-graphs
| volume = 192
| year = 1998| doi-access =
}}. 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.{{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}}.
The Rado graph is an infinite self-complementary graph.{{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.
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.{{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}}. 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.{{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}}.
References
{{reflist}}
External links
- {{mathworld|id=Self-ComplementaryGraph|title=Self-Complementary Graph|mode=cs2}}