Encyclopedia

Independence complex

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated April 1, 2026

The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets.

Every independent set in a graph is a clique in its complement graph, and vice versa. Therefore, the independence complex of a graph equals the clique complex of its complement graph, and vice versa.

01Homology groups

Several authors studied the relations between the properties of a graph G = (V, E), and the homology groups of its independence complex I(G). In particular, several properties related to the dominating sets in G guarantee that some reduced homology groups of I(G) are trivial.

1. The total domination number of G, denoted $\gamma _{0}(G)$ , is the minimum cardinality of a total dominating set of G - a set S such that every vertex of V is adjacent to a vertex of S. If $\gamma _{0}(G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$ .

2. The total domination number of a subset A of V in G, denoted $\gamma _{0}(G,A)$ , is the minimum cardinality of a set S such that every vertex of A is adjacent to a vertex of S. The independence domination number of G, denoted $i\gamma (G)$ , is the maximum, over all independent sets A in G, of $\gamma _{0}(G,A)$ . If $i\gamma (G)>k$ , then ${\tilde {H}}_{k-1}(I(G))=0$ .

3. The domination number of G, denoted $\gamma (G)$ , is the minimum cardinality of a dominating set of G - a set S such that every vertex of V \ S is adjacent to a vertex of S. Note that $\gamma _{0}(G)\geq \gamma (G)$ . If G is a chordal graph and $\gamma (G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$ .

4. The induced matching number of G, denoted $\mu (G)$ , is the largest cardinality of an induced matching in G - a matching that includes every edge connecting any two vertices in the subset. If there exists a subset A of V such that $\gamma _{0}(G,A)>k+\min[k,\mu (G[A])]$ then ${\tilde {H}}_{k-1}(I(G))=0$ . This is a generalization of both properties 1 and 2 above.

5. The non-dominating independence complex of G, denoted I'(G), is the abstract simplicial complex of the independent sets that are not dominating sets of G. Obviously I'(G) is contained in I(G); denote the inclusion map by $i:I'(G)\to I(G)$ . If G is a chordal graph then the induced map $i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))$ is zero for all $k\geq -1$ . This is a generalization of property 3 above.

6. The fractional star-domination number of G, denoted $\gamma _{s}^{*}(G)$ , is the minimum size of a fractional star-dominating set in G. If $\gamma _{s}^{*}(G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$ .

Watch videos about Independence complexExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Independence complex”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Independence complex.svg by BagLuke, CC0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Independence complex

01Homology groups

Sources and credits

Related topics

Rainbow-independent set

Independence complex

01Homology groups

02Related concepts

Sources and credits

Related topics

Rainbow-independent set