Self-complementary graph: Difference between revisions

Revision as of 19:52, 21 June 2022

Latest revision as of 21:21, 13 December 2023

(5 intermediate revisions by 4 users not shown)

Line 2:

[[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&nbspthinsp;×&nbspthinsp;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

Line 17:

| title = Complementary ''l''₁-graphs

| volume = 192

| year = 1998| doi-access = free

}}.</ref> All [[strongly regular graph|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.

Line 45:

==Properties==

An ''{{nowrap|{{mvar|n''}}-vertex}} self-complementary graph has exactly half numberas ofmany edges of the [[complete graph]], i.e., {{math|''n''(''n''&nbsp;&minus;&nbsp; − 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

Line 52:

| title = Über selbstkomplementäre Graphen

| volume = 9

| year = 1962}}.</ref> Since {{math|''n''(''n''&nbsp;&minus; − 1)}} must be divisible by 4, ''{{mvar|n''}} must be [[Congruencemodular relationarithmetic|congruent]] to 0 or 1 modmodulo 4; for instance, a {{nowrap|6-vertex}} graph cannot be self-complementary.

==Computational complexity==

Line 61:

==External links==

*{{mathworld|id=Self-ComplementaryGraph|title=Self-Complementary Graph|mode=cs2}}

[[Category:Graph families]]