Vertex Cover Polynomial
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
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).
graph Psi(x)
Andrásfai
graph A_n x^(2n-1)[x^n+(3n-1)(x+1)^(n-1)]
barbell graph x^(2n-2)(x+n+1)(x+n-1)
book graph S_(n+1)P_2 x{2[x(x+1)]^n+x[x(x+2)]^n}
cocktail party graph x^(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_n x^n+nx^(n-1)
complete
tripartite graph K_(n,n,n) 3[x^2(x+1)]^n-2x^(3n)
crown graph x^(2n-2)(n-x^2)+2[x+(x+1)]^n
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)
prism graph 2^(-n)[(-2)^nx^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x-+sqrt1+x(6+x))]^n]
star graph S_n x+(1+x)^(n-1)
sun
graph (1+x)^(n-2)[1+x(2+n+x)]
sunlet graph C_n circledot K_1 2^(-n)[(1+x-sqrt((1+x)(1+5x)))^n+(1+x+sqrt((1+x)(1+5x)))^n]
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).](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline51.svg){kind=link}
graph order recurrence
Andrásfai graph 3 p_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_n 3 p_n(x)=x^4p_(n-3)(x)+2x^3p_(n-2)(x)+x^2p_(n-1)(x)
barbell graph 3 p_n(x)=x^6p_(n-3)(x)-3x^4p_(n-2)(x)+3x^2p_(n-1)(x)
book graph S_(n+1)P_2 2 p_n(x)=-x^2(x+1)(x+2)p_(n-2)(x)+x(2n+3)p_(n-1)(x)
centipede graph 2 p_n(x)=(x+1)x^2p_(n-2)(x)+(x+1)xp_(n-1)(x)
cocktail party graph 2 p_n(x)=-x^4p_(n-2)(x)+2x^2p_(n-1)(x)
complete bipartite graph K_(n,n) 2 p_n(x)=-x^3(x+1)2p_(n-2)(x)+x(2x+1)p_(n-1)(x)
complete graph K_n 2 p_n(x)=-x^2p_(n-2)(x)+2xp_(n-1)(x)
complete tripartite graph K_(n,n,n) 2 p_n(x)=-x^5(x+1)p_(n-2)(x)+x^2(2x+1)p_(n-1)(x)
crossed prism graph 2 p_(2n)(x)=-x^4(2x^2+4x+1)p_(2n-2)(x)+x^2(x^2+4x+2)p_(2n-1)(x)
crown graph 3 p_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_n 2 p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
empty graph K^__n 1 p_n(x)=(x+1)p_(n-1)(x)
gear graph 3 p_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 graph 3 p_n(x)=-(x+1)^2x^3p_(n-3)(x)-(x+1)x^3p_(n-2)(x)+2(x+1)xp_(n-1)(x)
ladder graph 2 p_n(x)=x^3p_(n-2)(x)+(x+1)xp_(n-1)(x)
ladder rung graph 1 p_n(x)=x(x+2)p_(n-1)(x)
Möbius ladder M_n 3 p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
pan graph 2 p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
path graph P_n 2 p_n(x)=xp_(n-2)(x)+xp_(n-1)(x)
prism graph Y_n 3 p_n(x)=x^4p_(n-3)(x)+(2x+1)x^2p_(n-2)(x)+x^2p_(n-1)(x)
star graph S_n 2 p_n(x)=(-x-1)p_(n-2)(x)+(x+2)p_(n-1)(x)
sun graph 2 p_n(x)=2(x+1)p_(n-1)(x)-(x+1)^2p_(n-2)(x)
sunlet graph C_n circledot K_1 2 p_n(x)=x(x+1)p_(n-2)(x)+(x+1)p_(n-1)(x)
web graph 3 p_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_n 3 p_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 NumberExplore with Wolfram|Alpha
WolframAlpha
More things to try:
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.Referenced on Wolfram|Alpha
Vertex Cover PolynomialCite this as:
Weisstein, Eric W. "Vertex Cover Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexCoverPolynomial.html