Self-complementary graph: Difference between revisions

Revision as of 21:18, 8 January 2008

Revision as of 02:17, 10 March 2009

Line 2:

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

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 M.J., |last2=Colbourn|first2=Charles Ch.J. "|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>

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">[[Horst{{citation
| last = Sachs | first = Horst | authorlink = Horst Sachs,
| H.]]id (1962)= {{MR|0151953}}
| journal = Publicationes Mathematicae Debrecen
| pages = 270–288
| title = "Über selbstkomplementäre Graphen."
| ''Publ.volume Math.= Debrecen''9
| vol.year 9,= 270-2881962}}.</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.

Every [[Paley graph]] is self-complementary.<ref name="sachs"/>

==References==