Self-complementary graph
From Wikipedia, the free encyclopedia
A self-complementary graph is a graph which is isomorphic to its 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.[1]
An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3. [2] Since n(n −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.
Every Paley graph is self-complementary.
[edit] References
- ^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29
- ^ Sachs, H. (1962) "Über selbstkomplementäre Graphen." Publ. Math. Debrecen vol. 9, 270-288
