TOPICS
Search

Independence Polynomial


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

 I(x)=sum_(k=0)^(alpha(G))s_kx^k,
(1)

where alpha(G) is the independence number, is called the independence polynomial of G (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 L(G) correspond to independent vertex sets in the original graph G, the matching-generating polynomial of a graph G is equal to the independence polynomial of the line graph of G (Levit and Mandrescu 2005):

 mu_G(x)=I_(L(G))(x).
(2)

The independence polynomial is also related to the clique polynomial C_G(x) by

 C_G(x)=I_(G^_)(x),
(3)

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

 I_G(x)=x^nPsi_g(x^(-1)),
(4)

where n=|G| is the vertex count of G (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 x 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, s=sqrt(x^2+6x+1), t=sqrt(1+4x), and u=sqrt((x+1)(5x+1)).

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

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

The independence polynomial of a tree is unimodal, and the independence polynomial of a claw-free graph is logarithmically concave.


See also

Clique Polynomial, Independence Number, Independent Set, Lower Independence Number, Matching Polynomial

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Independence Polynomial

Cite this as:

Weisstein, Eric W. "Independence Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IndependencePolynomial.html

Subject classifications