Let c_k be the number of edge covers of a graph G of size k. Then the edge cover polynomial E_G(x) is defined by E_G(x) = sum_(k = 0)^m c_k x^k, where m is the edge count of G. Cycle graphs and complete bipartite graphs are determined by their edge cover polynomials. The edge cover polynomial is multiplicative over graph components, so for a graph G having connected components G_1, G_2, ..., the edge cover polynomial of G itself is given by E_G = E_(G_1) E_(G_2) ....

edge cover | edge cover number | vertex cover polynomial