Self-complementary graph: Difference between revisions

Revision as of 04:39, 8 January 2008

Revision as of 04:48, 8 January 2008

Line 4:

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>

An ''n''-vertex self-complementary graph has exactly half number of edges of the [[complete graph]], i.e., <math>''n''(''n-''&nbsp;&minus;&nbsp;1)/4</math> edges, and (if there is more than one vertex) it must have [[graph diameter|diameter]] either 2 or 3. <ref>[[Horst Sachs|Sachs, H.]] (1962) "Über selbstkomplementäre Graphen." ''Publ. Math. Debrecen'' vol. 9, 270-288</ref> Since ''n''(''n''&nbsp;&minus;1) must be divisible by 4, ''n'' must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

==References==