The vertex-cover polynomial of a graph (Q1613435): Difference between revisions

Let \(G\) be an undirected graph without multiple edges but possibly with loops. By an \(r\)-vertex cover in \(G\) we mean an \(r\)-element subset of the vertex set which has a common vertex with every edge in \(G\). Let \(\text{ cv}(G,r)\) be the number of \(r\)-vertex covers in \(G\). The authors study properties of the generating function (called the vertex-cover polynomial) of the sequence of numbers of \(r\)-vertex covers , i.e. the function \[ \Psi (G,\tau)=\sum_{r=0}^{v(G)}\text{cv}(G,r){\tau}^r. \] They show a recursive method of finding the vertex-cover polynomial for a given graph. Moreover, they compute the polynomial for several special classes of graphs. Finally, they show a relationship between their results and a problem in biological systematics.