Self-complementary graph: Difference between revisions

Revision as of 04:39, 8 January 2008

Latest revision as of 21:21, 13 December 2023

(35 intermediate revisions by 18 users not shown)

Line 1:

[[Image:Self-complementary{{short NZ graph.svg|thumbdescription|AGraph self-complementary graph: the blue Nwhich is isomorphic to its complement, the dashed red Z.]]}}

[[Image:Self-complementary NZ graph.svg|thumb|

A '''self-complementary graph''' is a [[graph (mathematics)|graph]] which is [[graph isomorphism|isomorphic]] to its [[graph complement|complement]]. The simplest self-complementary graphs are the 4-vertex [[path graph]] and the 5-vertex [[cycle graph]].

{{legend-line|solid #2878BD|Graph {{mvar|A}}}}

{{legend-line|dashed red|Graph complement of {{mvar|A}}}}

Graph {{mvar|A}} is isomorphic to its complement.]]

AIn the [[mathematical]] field of [[graph theory]], a '''self-complementary graph''' is a [[graph (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.

Self-complementary graphs are interesting in their relation to the [[graph isomorphism problem]]: 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>Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", ''[[SIGACT News]]'', 1978, vol. 10, no. 1, 25-29</ref>

==Examples==

An ''n''-vertex self-complementary graph has exactly half number of edges of the [[complete graph]], i.e., <math>n(n-1)/4</math> and [[graph diameter|diameter]] 2 or 3. <ref>[[Horst Sachs|Sachs, H.]] (1962) "Über selbstkomplementäre Graphen." ''Publ. Math. Debrecen'' vol. 9, 270-288</ref>

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

| issue = 1-3

| journal = Discrete Mathematics

| mr = 1656740

| pages = 323–331

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

| volume = 192

| year = 1998| doi-access =

}}.</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.

| 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 (graph theory)|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}}.</ref> Since {{math|''n''(''n'' − 1)}} must be divisible by 4, {{mvar|n}} must be [[modular arithmetic|congruent]] to 0 or 1 modulo 4; for instance, a {{nowrap|6-vertex}} graph cannot be self-complementary.

==Computational complexity==

Self-complementary graphs are interesting in their relation to the [[graph isomorphism problem]]: theThe 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 M.J., |last2=Colbourn|first2=Charles Ch.J.|author2-link=Charles "Colbourn|title=Graph isomorphism and self-complementary graphs", ''|journal=[[SIGACT News]]'', |year=1978, vol. |volume=10|issue=1|pages=25–29|doi=10, no. 1, 25-291145/1008605.1008608}}.</ref>

==References==

{{reflist}}

==External links==

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

[[Category:Graph families]]