Vertex Cover Polynomial
Let 
be the number of vertex covers of a graph 
of size 
. Then the vertex cover polynomial 
is defined by
 |
(1)
|
where 
is the vertex count of 
(Dong et al. 2002).
It is related to the independence polynomial 
by
 |
(2)
|
(Akban and Oboudi 2013).
Precomputed vertex cover polynomials for many named graphs in terms of a variable 
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 |
 |
Andrásfai graph  |
![x^(2n-1)[x^n+(3n-1)(x+1)^(n-1)]](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline11.svg) |
| barbell graph |
 |
book graph  |
![x<span style=]() {2[x(x+1)]^n+x[x(x+2)]^n}" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline14.svg" style="height:22px; width:240px" /> |
| cocktail party graph |
 |
complete bipartite graph  |
 |
complete bipartite graph  |
 |
complete graph  |
 |
complete tripartite graph  |
![3[x^2(x+1)]^n-2x^(3n)](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline23.svg) |
| crown graph |
![x^(2n-2)(n-x^2)+2[x+(x+1)]^n](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline24.svg) |
cycle graph  |
 |
empty graph  |
 |
| gear graph |
![[x(x+1)]^n+(x<span style=]() {[x(2+x-sqrt(x(4+x)))]^n+[x(2+x+sqrt(x(4+x)))]^n})/(2^n)" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline29.svg" style="height:34px; width:361px" /> |
| helm graph |
![[x(1+x)]^n+2^(-n)x<span style=]() {[x(1+x-sqrt((1+x)(5+x)))]^n+[x(1+x+sqrt((1+x)(5+x)))]^n}" src="https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline30.svg" style="height:28px; width:639px" /> |
ladder rung graph  |
![[x(x+2)]^n](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline32.svg) |
Möbius ladder  |
![(-2^n(-x)^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x+sqrt(1+x(6+x)))]^n)/(2^n)](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline34.svg) |
path graph  |
 |
| prism graph |
![2^(-n)[(-2)^nx^n+[x(1+x-sqrt(1+x(6+x)))]^n+[x(1+x-+sqrt1+x(6+x))]^n]](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline37.svg) |
star graph  |
 |
| sun graph |
![(1+x)^(n-2)[1+x(2+n+x)]](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline40.svg) |
sunlet graph  |
![2^(-n)[(1+x-sqrt((1+x)(1+5x)))^n+(1+x+sqrt((1+x)(1+5x)))^n]](https://mathworld.wolfram.com/images/equations/VertexCoverPolynomial/Inline42.svg) |
wheel graph  |
 |
Equivalent forms for the cycle graph 
include
| 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 |
 |
complete graph  |
2 |
 |
complete tripartite graph  |
2 |
 |
| crossed prism graph |
2 |
 |
| crown graph |
3 |
 |
cycle graph  |
2 |
 |
empty graph  |
1 |
 |
| 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 |
 |
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.
