Complement graph
In the mathematical field of graph theory, the complement or inverse of a graph Template:Mvar is a graph Template:Mvar on the same vertices such that two distinct vertices are adjacent (connected) in Template:Mvar if and only if they are not adjacent in Template:Mvar. 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]
The complement of the graph is not the set complement of the graph: only the edges are complemented.
Definitions
Let Template:Math be a simple undirected graph and let Template:Mvar consist of all pairs of distinct vertices in Template:Mvar. Then the simple undirected graph Template:Math is the complement of Template:Mvar,[2] where Template:Math is the relative complement of Template:Mvar in Template:Mvar.
Let Template:Math be a simple directed graph and let Template:Mvar consist of all ordered pairs of distinct vertices in Template:Mvar. Then the simple directed graph Template:Math is the complement of Template:Mvar.
Let Template:Mvar be a simple undirected / directed graph, let Template:Mvar be the complete simple undirected / directed graph on the same number of vertices (i.e., all entries are unity except the diagonal entries which are zero), let and respectively be the adjacency matrices of Template:Mvar and Template:Mvar. Then the adjacency matrix of the complement Template:Mvar of Template:Mvar is: .
The complement is not defined for multigraphs.
For graphs that allow self-loops (but not multiple adjacencies), the complement of a graph Template:Mvar may be defined by adding a self-loop to every vertex that does not have one in Template:Mvar, removing its self-loop from every vertex that has one in Template:Mvar, and otherwise using the same formula as above. However, this operation is different from the one for simple graphs, since applying it to a graph with no self-loop results in a graph with self-loops on all vertices.
Applications and examples
Several graph-theoretic concepts are related to each other via complementation:
- The complement of an edgeless graph is a complete graph, and vice versa.
- Any induced subgraph of the complement graph of a graph Template:Mvar is the complement of the corresponding induced subgraph in Template:Mvar.
- An independent set in a graph is a clique in the complement graph, and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph.
- The automorphism group of a graph is the automorphism group of its complement.
- The complement of every triangle-free graph is a claw-free graph,[3] but the reverse is not true.
Self-complementary graphs and graph classes
Template:Main 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. There is no known characterization of self-complementary graphs.
Several classes of graphs are self-complementary, in the sense that the complement of any graph in one of these classes is another graph in the same class.
- Perfect graphs are the graphs in which, for every induced subgraph, the chromatic number equals the size of the maximum clique. The fact that the complement of a perfect graph is also perfect is the perfect graph theorem of László Lovász.[4]
- Cographs are defined as the graphs that can be built up from single vertices by disjoint union and complementation operations. They form a self-complementary family of graphs: the complement of any cograph is another, different, cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their connected induced subgraphs has a disconnected complement. Another, self-complementary, definition is that cographs are the graphs with no four-vertex path as an induced subgraph.[5]
- Another self-complementary class of graphs is the class of split graphs, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph.[6]
- The threshold graphs are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a universal vertex (adjacent to all previously added vertices). These two operations are complementary and they generate a self-complementary class of graphs.[7]
Algorithmic aspects
In the analysis of algorithms on graphs, the distinction between a graph and its complement is an important one, because a sparse graph (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an implicit graph representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either depth-first search or breadth-first search on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size.[8] It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph.[8][9]