Independent Set

Two sets  and  are said to be independent if their intersection , where  is the empty set. For example,  and  are independent, but  and  are not. Independent sets are also called disjoint or mutually exclusive.

An independent vertex set of a graph  is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent vertex sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , 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.

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.