Independence number

Independence number --- число независимости, число внутренней устойчивости, неплотность.

For a graph [math]\displaystyle{ G }[/math], independence number [math]\displaystyle{ \beta(G) }[/math] is the size of a maximum independent set of [math]\displaystyle{ G }[/math]. The lower independence number [math]\displaystyle{ i(G) }[/math] is the minimum cardinality of a maximal independent set. (Because an independent set is maximally independent if and only if it is dominating, [math]\displaystyle{ i(G) }[/math] is also called the independent-domination number of [math]\displaystyle{ G }[/math].)

The other name is Stability number.

See also

• Transversal,
• Local independence number.