Independence Polynomial

Let  be the number of independent vertex sets of cardinality  in a graph . The polynomial

(1)

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):

(2)

The independence polynomial is also related to the clique polynomial  by

(3)

where  denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by

(4)

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 .

graph
Andrásfai graph
barbell graph
book graph
centipede graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
crossed prism graph
crown graph
cycle graph
gear graph
helm graph
ladder graph
ladder rung graph
Möbius ladder
pan graph
path graph
prism graph
star graph
sun graph
sunlet graph
triangular graph
wheel graph

The following table summarizes the recurrence relations for independence polynomials for some simple classes of graphs.

graph	order	recurrence
Andrásfai graph	3
antiprism graph	3
barbell graph	3
book graph	2
centipede graph	2
cocktail party graph	2
complete bipartite graph	2
crossed prism graph	2
crown graph	3
cycle graph	2
gear graph	3
helm graph	3
ladder graph	2
ladder rung graph	1
Möbius ladder	3
pan graph	2
path graph	2
prism graph	3
star graph	2
sun graph	2
sunlet graph	2
web graph	3
wheel graph	3

Nonisomorphic graphs do not necessarily have distinct independence polynomials. The following table summarizes some co-independence graphs.

	independence polynomial	graphs
4		, path graph
4		paw graph, square graph
5		,
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.

REFERENCES

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Chudnovsky, M. and Seymour, P. "The Roots of the Stable Set Polynomial of a Claw-Free Graph." 2004. http://www.math.princeton.edu/÷mchudnov/publications.html.

Gutman, I. and Harary, F. "Generalizations of the Matching Polynomial." Utilitas Mathematica 24, 97-106, 1983.

Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Disc. Math. 125, 219-228, 1994.

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 

(Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.