The graph complement of a graph, also called its complementary graph and sometimes
called the edge-complement (Gross and Yellen 2006, p. 86), is the graph, sometimes denoted or (e.g., Clark and Entringer 1983), with the same vertex
set but whose edge set consists of the edges
not present in
(i.e., the complement of the edge
set of
with respect to all possible edges on the vertex
set of ). The graph sum on an -nodegraph is therefore the complete
graph, as illustrated above.
For an indexed graph, a common convention is to write its complement as
, placing the bar over and leaving the subscript outside it. For example, the complement
of the complete graph is the empty graph (Papadima and Suciu 2006). Extending the bar over the
whole indexed expression, as in , denotes the same complement
(e.g.,
in Gross et al. 2014, p. 53).
Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica14, 57-68, 1983.Ellis-Monaghan,
J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations
and Interpretations." 28 Jun 2008. https://arxiv.org/abs/0806.4699.Gross,
J. L.; Yellen, J.; and Zhang, P. (Eds.). Handbook of Graph Theory, 2nd ed.
Boca Raton, FL: CRC Press, p. 53, 2014.Gross, J. T. and Yellen,
J. Graph
Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Papadima,
S. and Suciu, A. I. "Algebraic Invariants for Right-Angled Artin Groups."
Math. Ann.334, 533-555, 2006. https://doi.org/10.1007/s00208-005-0704-9.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.
, also called its complementary graph and sometimes
called the edge-complement (Gross and Yellen 2006, p. 86), is the graph 
, sometimes denoted 
or 
(e.g., Clark and Entringer 1983), with the same vertex
set but whose edge set consists of the edges
not present in 
(i.e., the complement of the edge
set of 
with respect to all possible edges on the vertex
set of 
). The graph sum 
on an 
-node graph 
is therefore the complete
graph 
, as illustrated above.
, a common convention is to write its complement as
, placing the bar over 
and leaving the subscript outside it. For example, the complement
of the complete graph 
is the empty graph 
(Papadima and Suciu 2006). Extending the bar over the
whole indexed expression, as in 
, denotes the same complement
(e.g., 
in Gross et al. 2014, p. 53).
of the graph complement of the graph
with adjacency matrix 
is given by
is the unit matrix and 
is the identity
matrix.
