Home Original page

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

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).

Equivalent forms for the cycle graph C_n include

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.

Referenced on Wolfram|Alpha

Vertex Cover Polynomial

Cite this as:

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

Subject classifications