Self-Complementary Graph -- from Wolfram MathWorld

Self-Complementary Graph

Download<br>Wolfram Notebook

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

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

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

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

The number of self-complementary graphs on nodes can be obtained from the "graph polynomial"

derived from P&oacute;lya's enumeration theorem used to enumerate the numbers of<br>simple graphs as .

All self-complementary symmetric graphs were identified by Peisert (2001). Peisert (2001) observed that graphs which are both symmetric<br>and self-complementary are necessarily strongly<br>regular, arc-transitive, and distance-transitive,<br>and proved that they are given by the Paley graphs,<br>Peisert graphs, and one exceptional graph on 529<br>vertices that is not isomorphic to either the 529-Paley<br>or 529-Peisert graph.

See also<br>Graph Complement, Isomorphic<br>Graphs

Explore with Wolfram|Alpha

More things to try:

self-complementary graph

1200 - 450

curl (curl F)

References<br>Camion, P. "Hamiltonian Chains in Self-Complementary Graphs." In Colloque sur la th&eacute;orie des graphes (Paris, 1974)<br>(Ed. P. P. Gillis and S. Huyberechts). Cahiers du Centre &Eacute;tudes<br>de Recherche Op&eacute;r. (Bruxelles) 17 , pp. 173-183, 1975.Clapham,<br>C. R. J. "Hamiltonian Arcs in Self-Complementary Graphs." Disc.<br>Math. 8 , 251-255, 1974.Farrugia, A. "Self-Complementary<br>Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999.<br>https://alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Peisert,<br>W. "All Self-Complementary Symmetric Graphs." J. Algebra 240 ,<br>209-229, 2001.Rao, S. B. "Cycles in Self-Complementary Graphs."<br>J. Combin. Th. |bf 22, 1-9, 1977.Read, R. C. "On the<br>Number of Self-Complementary Graphs and Digraphs." J. London Math. Soc. 38 ,<br>99-104, 1963.Read, R. C. and Wilson, R. J. An<br>Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Royle, G. "Self-Complementary<br>Graphs." http://school.maths.uwa.edu.au/~gordon/remote/selfcomp/Sachs,<br>H. "&Uuml;ber selbstkomplement&auml;re Graphen." Publ. Math. Debrecen 9 ,<br>270-288, 1962.Skiena, S. "Self-Complementary Graphs." &sect;5.2.3<br>in Implementing<br>Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,<br>MA: Addison-Wesley, p. 187, 1990.Sloane, N. J. A. Sequence<br>A000171/M0014 in "The On-Line Encyclopedia<br>of Integer Sequences."Wille, D. "Enumeration of Self-Complementary<br>Structures." J. Combin. Th. B 25 , 143-150, 1978.Referenced<br>on Wolfram|Alpha<br>Self-Complementary Graph

Cite this as:

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

Subject classifications

Created, developed and nurtured by Eric Weisstein at Wolfram Research