Self-complementary graph: Difference between revisions

Revision as of 02:48, 2 September 2011

Latest revision as of 21:21, 13 December 2023

(20 intermediate revisions by 10 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 non-trivial 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>{{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>

==Examples==

An ''n''-vertex self-complementary graph has exactly half number of edges of the [[complete graph]], i.e., ''n''(''n''&nbsp;&minus;&nbsp;1)/4 edges, and (if there is more than one vertex) it must have [[graph diameter|diameter]] either 2 or 3.<ref name="sachs">{{citation

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 = Sachs | first = Horst | authorlink = Horst Sachs

| last = Shpectorov | first = S.

| mr = 0151953

| doi = 10.1016/S0012-365X(98)0007X-1

| journal = [[Publicationes Mathematicae Debrecen]]

| pagesissue = 270–2881-3

| journal = Discrete Mathematics

| title = Über selbstkomplementäre Graphen

| volumemr = 91656740

| pages = 323–331

| year = 1962}}.</ref> Since ''n''(''n''&nbsp;&minus;1) must be divisible by 4, ''n'' must be [[Congruence relation|congruent]] to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

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

| volume = 192

Every [[Paley graph]] is self-complementary.<ref name="sachs"/> 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

| year = 1998| doi-access =

Every [[Paley graph]] is self-complementary }}.<ref name="sachs"/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

Line 25 ⟶ 30:

| 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 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

| journal = [[Publicationes Mathematicae Debrecen]]

| pages = 270–288

| 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==

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 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==

[[Category:Graph families]]

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

[[Category:Graph families]]

[[es:Grafo autocomplementario]]

[[pl:Graf samodopełniający]]