Let c_k be the number of vertex covers of a graph G of size k. Then the vertex cover polynomial Ψ_G(x) is defined by Ψ_G(x) = sum_(k = 0)^( left bracketing bar G right bracketing bar ) c_k x^k, where left bracketing bar G right bracketing bar is the vertex count of G . It is related to the independence polynomial I_G(x) by Ψ_G(x) = x^n I_G(x^(-1)) (Akban and Oboudi 2013).

edge cover polynomial | vertex cover | vertex cover number