The independence number of a graph is the cardinality of the largest independent set. Formally,

for a graph , where denotes the cardinality of the set . The independence number of the de Bruijn graph of order is given by 1, 2, 3, 7, 13, 28, ... (Sloane's A006946).

By definition, the independence number of a graph plus the number of elements in a minimal vertex cover of equals the number of vertices in the graph.

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.

Sloane, N. J. A. Sequence A006946/M0834 in "The On-Line Encyclopedia of Integer Sequences."

CITE THIS AS:

Weisstein, Eric W. "Independence Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/IndependenceNumber.html