Independence Complex
   HOME



picture info

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'') 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. 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'' ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Induced Matching
In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a Matching (graph theory), matching) and these are the only edges connecting any two vertices which are endpoints of the matching edges (it is an induced subgraph). An induced matching can also be described as an Independent set (graph theory), independent set in the Graph power, square of the line graph of the given graph. Strong coloring and neighborhoods The minimum number of induced matchings into which the edges of a graph can be partitioned is called its ''strong chromatic index'', by analogy with the chromatic index of the graph, the minimum number of matchings into which its edges can be partitioned. It equals the chromatic number of the square of the line graph. Brooks' theorem, applied to the square of the line graph, shows that the strong chromatic index is at most quadratic in the maximum degree of the given graph, but better ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  



MORE