Complement graph

Last updated June 24, 2023

In the mathematical field of 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]

Definition

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] where $K \ E$ is the relative complement of $E$ in $K$ . For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of $V$ in place of the set $K$ in the formula above. In terms of the adjacency matrix A of the graph, if Q is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of A is Q-A.

The complement is not defined for multigraphs. In graphs that allow self-loops (but not multiple adjacencies) the complement of $G$ may be defined by adding a self-loop to every vertex that does not have one in $G$ , and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result 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 $G$ is the complement of the corresponding induced subgraph in $G$ .
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] although the reverse is not true.

Self-complementary graphs and graph classes

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 they are the graphs with no induced subgraph in the form of a four-vertex path.^[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]

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex $v$ in a graph is a vertex that is connected to $v$ by an edge. The neighbourhood of a vertex $v$ in a graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$ , i.e., the graph composed of the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$ .

<span class="mw-page-title-main">Intersection graph</span> Graph representing intersections between given sets

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

<span class="mw-page-title-main">Threshold graph</span> Graph formed by adding isolated or universal vertices

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

Addition of a single isolated vertex to the graph.
Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum $k$ for which a clique cover exists is called the clique cover number of the given graph.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

References

1 2 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, 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 .
↑ Lovász, László (1972a), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics , 2 (3): 253–267, doi: 10.1016/0012-365X(72)90006-4 .
↑ Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics , 3 (3): 163–174, doi: 10.1016/0166-218X(81)90013-5 , MR 0619603 .
↑ Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, Theorem 6.1, p. 150, ISBN 0-12-289260-7, MR 0562306 .
↑ Golumbic, Martin Charles; Jamison, Robert E. (2006), "Rank-tolerance graph classes", Journal of Graph Theory, 52 (4): 317–340, doi:10.1002/jgt.20163, MR 2242832 .
1 2 Ito, Hiro; Yokoyama, Mitsuo (1998), "Linear time algorithms for graph search and connectivity determination on complement graphs", Information Processing Letters , 66 (4): 209–213, doi:10.1016/S0020-0190(98)00071-4, MR 1629714 .
↑ Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999), "Simple and efficient graph compression schemes for dense and complement graphs", Journal of Combinatorial Optimization, 2 (4): 351–359, doi:10.1023/A:1009720402326, MR 1669307 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[bm-1] 1 2 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, 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 .

[4] Lovász, László (1972a), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics , 2 (3): 253–267, doi: 10.1016/0012-365X(72)90006-4 .

[5] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics , 3 (3): 163–174, doi: 10.1016/0166-218X(81)90013-5 , MR 0619603 .

[6] Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, Theorem 6.1, p. 150, ISBN 0-12-289260-7, MR 0562306 .

[7] Golumbic, Martin Charles; Jamison, Robert E. (2006), "Rank-tolerance graph classes", Journal of Graph Theory, 52 (4): 317–340, doi:10.1002/jgt.20163, MR 2242832 .

[iy98-8] 1 2 Ito, Hiro; Yokoyama, Mitsuo (1998), "Linear time algorithms for graph search and connectivity determination on complement graphs", Information Processing Letters , 66 (4): 209–213, doi:10.1016/S0020-0190(98)00071-4, MR 1629714 .

[9] Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999), "Simple and efficient graph compression schemes for dense and complement graphs", Journal of Combinatorial Optimization, 2 (4): 351–359, doi:10.1023/A:1009720402326, MR 1669307 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]