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 , but may also be written
(e.g., Burger et al. 1997)
or
(e.g., Bollobás 1981).
The independence number of a graph is equal to the largest exponent in the graph's independence polynomial.
The lower independence number may be similarly defined as the size of a smallest maximal
independent vertex set in
(Burger et al. 1997).
The lower irredundance number , lower domination number
, lower
independence number
, upper independence number
, upper domination
number
,
and upper irredundance number
satsify the chain of inequalities
(1)
|
(Burger et al. 1997).
The ratio of the independence number of a graph to its vertex count is known
as the independence ratio of
(Bollobás 1981).
The independence number of a graph is equal to the clique number
of the complement graph,
(2)
|
For a connected regular graph
on
vertices with vertex degree
and smallest graph eigenvalue
,
(3)
|
(A. E. Brouwer, pers. comm., Dec. 17, 2012).
For
the graph radius,
(4)
|
(DeLa Vina and Waller 2002). Lovasz (1979, p. 55) showed that when is the path covering
number,
(5)
|
with equality for only complete graphs (DeLa Vina and Waller 2002).
The matching number of a graph
is equal to the independence number
of its line graph
.
By definition,
(6)
|
where
is the vertex cover number of
and
its vertex count (West
2000).
Known value for some classes of graph are summarized below.
graph | OEIS | values | |
alternating group
graph | A000000 | 1, 1, 4, 20, 120, ... | |
A000027 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | ||
A004523 | 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ... | ||
A000244 | 1, 3, 9, 27, 81, 243, 729, 2187, ... | ||
complete bipartite graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
complete graph | 1 | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
complete tripartite graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
cycle graph | A004526 | 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ... | |
empty graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
A058622 | 1, 1, 4, 5, 16, 22, 64, 93, 256, ... | ||
grid
graph | A000982 | 1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... | |
grid graph | A036486 | 1, 4, 14, 32, 63, 108, 172, 256, 365, 500, ... | |
A005864 | 1, 1, 4, 5, 16, 22, 64, 93, 256, ... | ||
A000244 | 1, 3, 9, 27, 81, 243, 729, 2187, ... | ||
hypercube graph | A000079 | 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... | |
A258935 | 4, 5, 8, 16, 32, 64, 128, 256, 512, ... | ||
A008794 | 1, 4, 4, 9, 9, 16, 16, 25, 25 | ||
A030978 | 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... | ||
Kneser graph | |||
A266550 | 1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... | ||
Möbius ladder | A109613 | 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ... | |
odd graph | A000000 | 1, 1, 4, 15, 56, 210, 792, 3003, 11440, ... | |
A000000 | 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ... | ||
path graph | A004526 | 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ... | |
prism graph | A052928 | 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ... | |
4, 32, 256, ... | |||
1, 3, 6, 15, 42, ... | |||
star graph | A028310 | 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... | |
triangular graph | A004526 | 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ... | |
A032766 | 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ... | ||
wheel graph | A004526 | 1, 2, 2, 3, 3, 4, 4, 5, 5, ... |
Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "IndependenceNumber"].