The vertex-cover polynomial of a graph
by
Kee Teo
Institute of Fundamental Sciences, Massey University

Let G be a graph that contains no multiple edges but may have loops. A subset S of the vertex set of G is an r-vertex cover of G if |S|=r and S \cap {x, y} =/= \emptyset for each edge xy of G. Let cv(G) be the number of r-vertex covers of G. The vertex cover polynomial of G is the polynomial

\Psi(G, \tau)= n å r=0  cv(G, r)\taur,

where n is the number of vertices of G.

In this talk we give a reduction method for computing this polynomial. Simple examples using this method will be shown. We show how this polynomial is related to the problem of finding the number of functions f from {1, 2, ... , m}, for any positive integer m, into the vertex set subject to f^-1(x) \cap f^-1(y) =/= \emptyset.

Date received: October 18, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caek-69.