Vertex-cover polynomial

Vertex-cover polynomial --- многочлен вершинных покрытий.

Let [math]\displaystyle{ {\mathcal CV}(G,r) }[/math] be the set of [math]\displaystyle{ r }[/math]-vertex covers in [math]\displaystyle{ G }[/math], and [math]\displaystyle{ cv(G,r) = |{\mathcal CV}(G,r)| }[/math]. We define the following generating function:

[math]\displaystyle{ \Psi(G,\tau) = \sum^{v=|V(G)|}_{v=0} cv(G,r)\tau^{r}. }[/math]

It is natural to call [math]\displaystyle{ \Psi(G,\tau) }[/math] the vertex-cover polynomial of [math]\displaystyle{ G }[/math].