Independence complex

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") indeed meets the requirement of an abstract simplicial complex that every subset of a set in the family should also be in the family.
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.
Homology 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 formula_1, 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 formula_2 then formula_3.
2. The "total domination number" of a subset "A" of "V" in G, denoted formula_4, 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 formula_5, is the maximum, over all independent sets "A" in "G", of formula_4. If formula_7, then formula_3.
3. The "domination number" of "G", denoted formula_9, 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 formula_10. If "G" is a chordal graph and formula_11 then formula_3.
4. The "induced matching number" of "G", denoted formula_13, 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 formula_14 then formula_3. 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 formula_16. If "G" is a chordal graph then the induced map formula_17 is zero for all formula_18. This is a generalization of property 3 above.
6. The "fractional star-domination number" of G, denoted formula_19, is the minimum size of a fractional star-dominating set in "G". If formula_20 then formula_3.
Related concepts.
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".
The ("m","n")-chessboard complex is the matching complex on the complete bipartite graph "Km,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.
The clique complex of G is the independence complex of the complement graph of "G".