TOPICS
Search

Independence Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The independence polynomial of a graph G is the polynomial

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

where s_k is the number of independent vertex sets of cardinality k in G and alpha(G) is the independence number (Gutman and Harary 1983, Levit and Mandrescu 2005). It 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)).

graphI(x)
Andrásfai graph A_n1+(3n-1)x(x+1)^(n-1)
barbell graph[1+(n-1)x][1+(n+1)x]
book graph S_(n+1) square P_22x(1+x)^n+(1+2x)^n
centipede graph((-1+u-3x)(1-u+x)^n+(1+u+x)^n(1+u_3x))/(2^(n+1)u)
cocktail party graph K_(n×2)1+nx(x+2)
complete bipartite graph K_(n,n)2(x+1)^n-1
complete graph K_n1+nx
complete tripartite graph K_(n,n,n)3(x+1)^n-2
crossed prism graph2^(-n)[(1+2x(2+x)-sqrt((1+2x)(1+6x)))^n+(1+2x(2+x)+sqrt((1+2x)(1+6x)))^n]
crown graph2(x+1)^n+nx^2-1
cycle graph C_n2(-x)^(n/2)T_n(1/(2sqrt(-x)))
gear graphx(x+1)^n+((1-t+2x)^n+(1+t+2x)^n)/(2^n)
helm graph2^(-n)[2^nx(+x+1)^n+(x-u+1)^n+(x+u+1)^n]
ladder graph2^(-(n+1))[(s-3x-1)(x-s+1)^n+(s+3x+1)(x+s+1)^n]
ladder rung graph nP_2(2x+1)^n
Möbius ladder M_n2^(-n)[-2^n(-x)^n+(x-s+1)^n+(x+s+1)^n]
pan graph((1-t)^n(-x+t(2+x))+(1+t)^n(x+t(2+x)))/(2^(n+1)t)
path graph P_nx^((n+1)/2)F_(n+2)(x^(-1/2))
prism graph2^(-n)[2^n(-x)^n+(1+x-s)^n+(1+x+s)^n]
star graph S_nx+(1+x)^(n-1)
sun graph(x+1)^(n-2)[1+x(x+n+2)]
sunlet graph C_n circledot K_12^(-n)[(u+x+1)^n+(-u+x+1)^n]
triangular graph2^(-n/2)(-isqrt(x))^nH_n(i/(sqrt(2x)))
=2^(n/2)(-1/x)^(-n/2)U(1/2n,1/2,1/(2x))
wheel graph W_n(-(1-t)^n-(1-t)^nt+(t-1)(1+t)^n+2^(n-1)x^2)/(2^(n+1)x)

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

graphorderrecurrence
Andrásfai graph3p_n(x)=(2x+3)p_(n-1)(x)-(x+1)(x+3)p_(n-2)(x)+(x+1)^2p_(n-3)(x)
antiprism graph3p_n(x)=x^2p_n-3(x)+2xp_n-2(x)+p_n-1(x)
barbell graph3p_n(x)=3p_(n-1)(x)-3p_(n-2)(x)+p_(n-3)(x)
book graph S_(n+1) square P_22p_n(x)=(3x+2)p_(n-1)(x)-(x+1)(2x+1)p_(n-2)(x)
centipede graph2p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
cocktail party graph K_(n×2)2p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
complete bipartite graph K_(n,n)2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
crossed prism graph2p_n(x)=(2x^2+4x+1)p_(n-1)(x)-x^2(x^2+4x+2)p_(n-2)(x)
crown graph3p_n(x)=(x+3)p_(n-1)(x)-(2x+3)p_(n-2)(x)+(x+1)p_(n-3)(x)
cycle graph C_n2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
gear graph3p_n(x)=(3x+2)p_(n-1)(x)-(3x^2+3x+1)p_(n-2)(x)+(x+1)x^2p_(n-3)(x)
helm graph3p_n(x)=2(x+1)p_(n-1)(x)-(x+1)p_(n-2)(x)-x(x+1)^2p_(n-3)(x)
ladder graph2p_n(x)=(x+1)p_(n-1)(x)+xp_(n-2)(x)
ladder rung graph1p_n(x)=(2x+1)p_(n-1)(x)
Möbius ladder M_n3p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
pan graph2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
path graph P_n2p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
prism graph Y_n3p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
star graph S_n2p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
sun graph2p_n(x)=2(x+1)p_(n-1)(x)-(x+1)^2p_(n-2)(x)
sunlet graph C_n circledot K_12p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
web graph3p_n(x)=(x+1)p_(n-1)(x)+2x(x+1)^2p_(n-2)(x)+x^2(x+1)^2p_(n-3)(x)
wheel graph W_n3p_n(x)=2p_(n-1)(x)+(x-1)p_(n-2)(x)-xp_(n-3)(x)

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

nindependence polynomialgraphs
4(1+x)(1+3x)(4,6), path graph P_4
41+4x+2x^2paw graph, square graph
5(1+x)^2(1+3x)(5,8), (5,9)
5(1+x)(1+4x)butterfly graph, house graph, kite graph, (5,24)
5(1+x)(1+4x+x^2)banner graph, bull graph, (5,15)
5(1+x)(1+4x+2x^2)fork graph, (5,10), (5,14)
51+5x+2x^2house X graph, wheel graph W_5
51+5x+3x^2gem graph, (5,31), (4,1)-lollipop graph
51+5x+5x^2cycle graph C_5, (3,2)-tadpole graph
51+5x+4x^2+x^3dart graph, complete bipartite graph K_(2,3)

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. https://web.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 Resource. https://mathworld.wolfram.com/IndependencePolynomial.html

Subject classifications