TOPICS
Search

Independent Set


Two sets A and B are said to be independent if their intersection A intersection B=emptyset, where emptyset is the empty set. For example, {A,B,C} and {D,E} are independent, but {A,B,C} and {C,D,E} are not. Independent sets are also called disjoint or mutually exclusive.

IndependentSet

An independent vertex set of a graph G is a subset of the vertices such that no two vertices in the subset represent an edge of G. The figure above shows independent vertex sets consisting of two subsets for a number of graphs (the wheel graph W_8, utility graph K_(3,3), Petersen graph, and Frucht graph).

An independent edge set can be defined similarly (Skiena 1990, p. 219).

A maximal independent set is an independent set which is a maximal set, i.e., an independent set that is not a subset of any other independent set.


See also

Clique, Disjoint Sets, Edge Cover, Empty Set, Independence Number, Independence Polynomial, Independent Edge Set, Independent Vertex Set, Intersection, Maximal Independent Edge Set, Maximal Independent Set, Maximal Independent Vertex Set, Maximum Independent Edge Set, Maximum Independent Set Problem, Maximum Independent Vertex Set, Venn Diagram, Vertex Cover

Explore with Wolfram|Alpha

References

Hochbaum, D. S. (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing, p. 125, 1997.Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Referenced on Wolfram|Alpha

Independent Set

Cite this as:

Weisstein, Eric W. "Independent Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IndependentSet.html

Subject classifications