TOPICS
Search

Self-Complementary Graph


SelfComplementaryGraphs

A self-complementary graph is a graph which is isomorphic to its graph complement. The numbers of simple self-complementary graphs on n=1, 2, ... nodes are 1, 0, 0, 1, 2, 0, 0, 10, ... (OEIS A000171). The first few of these correspond to the trivial graph on one node, the path graph P_4, and the cycle graph C_5.

Every self-complementary graph is not only connected, but also traceable (Clapham 1974; Camion 1975; Farrugia 1999, p. 52). Furthermore, all self-complementary graphs have graph diameter 2 or 3 (Sachs 1962; Skiena 1990, p. 187). For a self-complementary graph on n>5 vertices, there is a graph cycle of length l for every integer 3<=l<=n-2 (Rao 1977; Farrugia 1999, p. 51). As a result, the graph circumference of a self-complementary graph on n>5 vertices is either n (i.e., the graph is Hamiltonian), n-1, or n-2 (Furrigia 1999, p. 51).

By definition, a self-complementary graph must have exactly half the total possible number of edges, i.e., n(n-1)/4 edges for a self-complementary graph on n vertices. Since n(n-1) must be divisible by 4, it follows that n=0 or 1 (mod 4).

There is a polynomial-time condition to determine if a self-complementary graph is Hamiltonian.

The number of self-complementary graphs on n nodes can be obtained from the "graph polynomial" P_n(x) derived form Pólya's enumeration theorem used to enumerate the numbers of simple graphs as P_n(-1).


See also

Graph Complement, Isomorphic Graphs

Explore with Wolfram|Alpha

References

Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la théorie des graphes (Paris, 1974) (Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre Études de Recherche Opér. (Bruxelles) 17, pp. 173-183, 1975.Clapham, C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc. Math. 8, 251-255, 1974.Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Rao, S. B. "Cycles in Self-Complementary Graphs." J. Combin. Th. |bf 22, 1-9, 1977.Read, R. C. "On the Number of Self-Complementary Graphs and Digraphs." J. London Math. Soc. 38, 99-104, 1963.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Sachs, H. "Über selbstkomplementäre Graphen." Publ. Math. Debrecen 9, 270-288, 1962.Skiena, S. "Self-Complementary Graphs." §5.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 187, 1990.Sloane, N. J. A. Sequence A000171/M0014 in "The On-Line Encyclopedia of Integer Sequences."Wille, D. "Enumeration of Self-Complementary Structures." J. Combin. Th. B 25, 143-150, 1978.

Referenced on Wolfram|Alpha

Self-Complementary Graph

Cite this as:

Weisstein, Eric W. "Self-Complementary Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Self-ComplementaryGraph.html

Subject classifications