Self-complementary graph: Difference between revisions

Revision as of 00:13, 18 March 2013

Latest revision as of 21:21, 13 December 2023

(16 intermediate revisions by 8 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.

==Examples==

Every [[Paley graph]] is self-complementary.<ref name="sachs"/> AllFor example, the 3&thinsp;×&thinsp;3 [[strongly regularrook's graph|strongly regular]] (the Paley graph of order nine) is self-complementary, graphsby witha fewersymmetry thanthat 37keeps verticesthe arecenter Paleyvertex graphs;in however,place therebut areexchanges stronglythe regularroles graphsof onthe 37,four 41,side midpoints and 49four verticescorners thatof are not Paleythe graphsgrid.<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

Line 15 ⟶ 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

Line 25 ⟶ 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 32 ⟶ 59:

==References==

{{reflist}}

==External links==

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

[[Category:Graph families]]