upper independence number | vertex independence number

The (upper) vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set (which is the same as the size of a largest maximal independent vertex set). The independence number is most commonly denoted α(G), but may also be written β(G) (e.g., Burger et al. 1997) or β_0(G). The independence number of a graph is equal to the largest exponent in the graph's independence polynomial. The lower independence number i(G) may be similarly defined as the size of a smallest maximal independent vertex set in G .

clique number | independence polynomial | independence ratio | independent set | lower independence number | matching number | maximum independent vertex set | minimum vertex cover | Shannon capacity | vertex cover