Complement graph
.svg?lang=en)
The Petersen graph as Kneser graph KG(5,2) ...
.svg?lang=en)
... and its complement the Johnson graph J(5,2)
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 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 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 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.[4]
- 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.[5]
- 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.[6]
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..
- ^ 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.
- ^ Bailey, Robert F.; Cáceres, José; Garijo, Delia; González, Antonio; Márquez, Alberto; Meagher, Karen; Puertas, María Luz (2013), "Resolving sets for Johnson and Kneser graphs", European Journal of Combinatorics, 34 (4): 736–751, doi:10.1016/j.ejc.2012.10.008, MR 3010114.