Independence complex

Several authors studied the relations between the properties of a graph G = (V, E), and the homology groups of its independence complex I(G).[1] 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 ${\displaystyle \gamma _{0}(G)}$, is the minimum cardinality of a set total dominating set of G - a set S such that every vertex of V is adjacent to a vertex of S. If ${\displaystyle \gamma _{0}(G)>k}$ then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.[2]

2. The total domination number of a subset A of V in G, denoted ${\displaystyle \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 ${\displaystyle i\gamma (G)}$, is the maximum, over all independent sets A in G, of ${\displaystyle \gamma _{0}(G,A)}$. If ${\displaystyle i\gamma (G)>k}$, then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.[1][3]

3. The domination number of G, denoted ${\displaystyle \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 ${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$. If G is a chordal graph and ${\displaystyle \gamma (G)>k}$ then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.[4]

4. The induced matching number of G, denoted ${\displaystyle \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 ${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$ then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.[5] 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 ${\displaystyle i:I'(G)\to I(G)}$. If G is a chordal graph then the induced map ${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$ is zero for all ${\displaystyle k\geq -1}$.[1]^:Thm.1.4 This is a generalization of property 3 above.

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

Meshulam's game is a game played on a graph G, that can be used to calculate a lower bound on the homological connectivity of the independence complex of G.

The matching complex of a graph G, denoted M(G), is an abstract simplicial complex of the matchings in G. It is the independence complex of the line graph of G.[6][7]

The (m,n)-chessboard complex is the matching complex on the complete bipartite graph K_m,_n. It is the abstract simplicial complex of all sets of positions on an m-by-n chessboard, on which it is possible to put rooks without each of them threatening the other.[8][9]

The clique complex of G is the independence complex of the complement graph of G.

• Rainbow-independent set