TOPICS
Search

Vertex Cover Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Let c_k be the number of vertex covers of a graph G of size k. Then the vertex cover polynomial Psi_G(x) is defined by

Psi_G(x)=sum_(k=0)^(|G|)c_kx^k,
(1)

where |G| is the vertex count of G (Dong et al. 2002).

It is related to the independence polynomial I_G(x) by

Psi_G(x)=x^nI_G(x^(-1))
(2)

(Akban and Oboudi 2013).

Precomputed vertex cover polynomials for many named graphs in terms of a variable x can be obtained in the Wolfram Language using GraphData[graph, "VertexCoverPolynomial"][x].

The following table summarizes closed forms for the vertex cover polynomials of some common classes of graphs (cf. Dong et al. 2002).

graphPsi(x)
Andrásfai graph A_nx^(2n-1)[x^n+(3n-1)(x+1)^(n-1)]
barbell graphx^(2n-2)(x+n+1)(x+n-1)
book graph S_(n+1)P_2x{2[x(x+1)]^n+x[x(x+2)]^n}
cocktail party graphx^(2n-2)(n+2nx+x^2)
complete bipartite graph K_(m,n)x^m(1+x)^n+x^n(1+x)^m-x^(m+n)
complete bipartite graph K_(n,n)2x^n(x+1)^n-x^(2n)
complete graph K_nx^n+nx^(n-1)
complete tripartite graph K_(n,n,n)3[x^2(x+1)]^n-2x^(3n)
crown graphx^(2n-2)(n-x^2)+2[x+(x+1)]^n
cycle graph C_nsum_(k=1)^(n)n/k(k; n-k)x^k
empty graph K^__n(1+x)^n
gear graph[x(x+1)]^n+(x{[x(2+x-sqrt(x(4+x)))]^n+[x(2+x+sqrt(x(4+x)))]^n})/(2^n)
helm graph[x(1+x)]^n+2^(-n)x{[x(1+x-sqrt((1+x)(5+x)))]^n+[x(1+x+sqrt((1+x)(5+x)))]^n}
ladder rung graph nP_2[x(x+2)]^n
Möbius ladder M_n(-2^n(-x)^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x+sqrt(1+x(6+x)))]^n)/(2^n)
path graph P_nsum_(k=0)^(n)(k+1; n-k)x^k
prism graph2^(-n)[(-2)^nx^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x-+sqrt1+x(6+x))]^n]
star graph S_nx+(1+x)^(n-1)
sun graph(1+x)^(n-2)[1+x(2+n+x)]
sunlet graph C_n circledot K_12^(-n)[(1+x-sqrt((1+x)(1+5x)))^n+(1+x+sqrt((1+x)(1+5x)))^n]
wheel graph W_nx^(n-1)+sum_(k=2)^(n)(n-1)/(k-1)(k-1; n-k)x^k

Equivalent forms for the cycle graph C_n include

Psi_(C_n)=sum_(k=1)^(n)n/k(k; n-k)x^k
(3)
=([x-sqrt(x(4+x))]^n+[x+sqrt(x(4+x))]^n)/(2^n).
(4)
graphorderrecurrence
Andrásfai graph3p_n(x)=(x+1)^2x^2p_(n-3)(x)-(x+1)(3x+1)x^4p_(n-2)(x)+(3x+2)x^2p_(n-1)(x)
antiprism graph Y_n3p_n(x)=x^4p_(n-3)(x)+2x^3p_(n-2)(x)+x^2p_(n-1)(x)
barbell graph3p_n(x)=x^6p_(n-3)(x)-3x^4p_(n-2)(x)+3x^2p_(n-1)(x)
book graph S_(n+1)P_22p_n(x)=-x^2(x+1)(x+2)p_(n-2)(x)+x(2n+3)p_(n-1)(x)
centipede graph2p_n(x)=(x+1)x^2p_(n-2)(x)+(x+1)xp_(n-1)(x)
cocktail party graph2p_n(x)=-x^4p_(n-2)(x)+2x^2p_(n-1)(x)
complete bipartite graph K_(n,n)2p_n(x)=-x^3(x+1)2p_(n-2)(x)+x(2x+1)p_(n-1)(x)
complete graph K_n2p_n(x)=-x^2p_(n-2)(x)+2xp_(n-1)(x)
complete tripartite graph K_(n,n,n)2p_n(x)=-x^5(x+1)p_(n-2)(x)+x^2(2x+1)p_(n-1)(x)
crossed prism graph2p_(2n)(x)=-x^4(2x^2+4x+1)p_(2n-2)(x)+x^2(x^2+4x+2)p_(2n-1)(x)
crown graph3p_n(x)=x^5(x+1)p_(n-3)(x)-(3x+2)x^3p_(n-2)(x)+(3x+1)xp_(n-1)(x)
cycle graph C_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
empty graph K^__n1p_n(x)=(x+1)p_(n-1)(x)
gear graph3p_n(x)=(x+1)x^3p_(n-3)(x)-(x^2+3x+3)x^2p_(n-2)(x)+(2x+3)xp_(n-1)(x)
helm graph3p_n(x)=-(x+1)^2x^3p_(n-3)(x)-(x+1)x^3p_(n-2)(x)+2(x+1)xp_(n-1)(x)
ladder graph2p_n(x)=x^3p_(n-2)(x)+(x+1)xp_(n-1)(x)
ladder rung graph1p_n(x)=x(x+2)p_(n-1)(x)
Möbius ladder M_n3p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
pan graph2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
path graph P_n2p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
prism graph Y_n3p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
star graph S_n2p_n(x)=(-x-1)p_(n-2)(x)+(x+2)p_(n-1)(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(x+1)p_(n-2)(x)+(x+1)p_(n-1)(x)
web graph3p_n(x)=(x+1)^2x^5p_(n-3)(x)+2(x+1)^2x^3p_(n-2)(x)+(x+1)x^2p_(n-1)(x)
wheel graph W_n3p_n(x)=-xp_(n-3)(x)+(x-1)p_(n-2)(x)+2p_(n-1)(x)

See also

Edge Cover Polynomial, Vertex Cover, Vertex Cover Number

Explore with Wolfram|Alpha

References

Akban, S. and Oboudi, M. R. "On the Edge Cover Polynomial of a Graph." Europ. J. Combin. 34, 297-321, 2013.Csikvári, P. and Oboudi, M. R. "On the Roots of Edge Cover Polynomials of Graphs." Europ. J. Combin. 32, 1407-1416, 2011.Dong, F. M.; Hendy, M. D.; Teo, K. L.; and Little, C. H. C. "The Vertex-Cover Polynomial of a Graph." Discr. Math. 250, 71-78, 2002.

Cite this as:

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

Subject classifications