Graph Complement

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The complement of a graph 👁 G
, sometimes called the edge-complement (Gross and Yellen 2006, p. 86), is the graph 👁 G^'
, sometimes denoted 👁 G^_
or 👁 G^c
(e.g., Clark and Entringer 1983), with the same vertex set but whose edge set consists of the edges not present in 👁 G
(i.e., the complement of the edge set of 👁 G
with respect to all possible edges on the vertex set of 👁 G
). The graph sum 👁 G+G^_
on a 👁 n
-node graph 👁 G
is therefore the complete graph 👁 K_n
, as illustrated above.

The adjacency matrix 👁 A^_
of the graph complement of the graph with adjacency matrix 👁 A
is given by

(Ellis-Monaghan and Merino 2008), where 👁 J
is the unit matrix and 👁 I
is the identity matrix.

A graph complement can be computed in the Wolfram Language by the command [g].

See also

Complement, Complete Graph, Cycle Complement Graph, Graph Sum, Path Complement Graph, Rook Complement Graph, Self-Complementary Graph, Wheel Complement Graph

Explore with Wolfram|Alpha

References

Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Skiena, S. "The Complement of a Graph." §3.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 93, 1990.

Referenced on Wolfram|Alpha

Graph Complement

Cite this as:

Weisstein, Eric W. "Graph Complement." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphComplement.html

Subject classifications