Let be the number of independent vertex sets of cardinality in a graph . The polynomial
where is the independence number, is called the independence polynomial of (Gutman and Harary 1983, Levit and Mandrescu 2005). It is also goes by several other names, including the independent set polynomial (Hoede and Li 1994) or stable set polynomial (Chudnovsky and Seymour 2004).
The independence polynomial is closely related to the matching polynomial. In particular, since independent edge sets in the line graph correspond to independent vertex sets in the original graph , the matching-generating polynomial of a graph is equal to the independence polynomial of the line graph of (Levit and Mandrescu 2005):
The independence polynomial is also related to the clique polynomial by
where denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by
where is the vertex count of (Akban and Oboudi 2013).
The independence polynomial of a disconnected graph is equal to the product of independence polynomials of its connected components.
Precomputed independence polynomials for many named graphs in terms of a variable can be obtained in the Wolfram Language using GraphData[graph, "IndependencePolynomial"][x].
The following table summarizes closed forms for the independence polynomials of some common classes of graphs. Here, , , and .
|Andrásfai graph |
|book graph |
|cocktail party graph |
|complete bipartite graph |
|complete graph |
|complete tripartite graph |
|crossed prism graph|
|cycle graph |
|ladder rung graph |
|Möbius ladder |
|path graph |
|star graph |
|sunlet graph |
|wheel graph |
The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.
|book graph ||2|
|cocktail party graph ||2|
|complete bipartite graph ||2|
|crossed prism graph||2|
|cycle graph ||2|
|ladder rung graph||1|
|Möbius ladder ||3|
|path graph ||2|
|prism graph ||3|
|star graph ||2|
|sunlet graph ||2|
|wheel graph ||3|
Nonisomorphic graphs do not necessarily have distinct independence polynomials. The following table summarizes some co-independence graphs.
|4||, path graph |
|4||paw graph, square graph|
|5||butterfly graph, house graph, kite graph, |
|5||banner graph, bull graph, |
|5||fork graph, , |
|5||house X graph, wheel graph |
|5||gem graph, , -lollipop graph|
|5||cycle graph , -tadpole graph|
|5||dart graph, complete bipartite graph |
The independence polynomial of a tree is unimodal, and the independence polynomial of a claw-free graph is logarithmically concave.