TOPICS
Search

Graph Complement


GraphComplement

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

 A^_=J-I-A

(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 GraphComplement[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 Web Resource. https://mathworld.wolfram.com/GraphComplement.html

Subject classifications