Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.^[1] It is not, however, the set complement of the graph; only the edges are complemented.

Formal construction

Let G = (V, E) be a simple graph and let K consist of all 2-element subsets of V. Then H = (V, K \ E) is the complement of G.^[2]

Applications and examples

Several graph-theoretic concepts are related to each other via complement graphs:

The vertices of the Kneser graph KG(n,k) are the k-subsets of an n-set, and the edges are between disjoint sets. The complement is the Johnson graph J(n,k), where the edges are between intersecting sets.
The complement of an edgeless graph is a complete graph and vice versa.
An independent set in a graph is a clique in the complement graph and vice versa.
The complement of every triangle-free graph is a claw-free graph,^[3] although the reverse is not true.
A self-complementary graph is a graph that is isomorphic to its own complement.^[1] Examples include the four-vertex path graph and five-vertex cycle graph.
Cographs are defined as the graphs that can be built up from disjoint union and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.

References

^ ^a ^b Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications (PDF), North-Holland, p. 6, ISBN 0-444-19451-7.
^ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.
^ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs" (PDF), Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738..

[bm-1] Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications (PDF), North-Holland, p. 6, ISBN 0-444-19451-7.

[2] Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.

[3] Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs" (PDF), Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738..

[1]

[2]

[3]