Well-covered weightings of graphs
by
R. J. Nowakowski
Dalhousie University
Coauthors: J. I. Brown, Dalhousie University

Following recent papers of Caro, Ellingham and others, a weighting of the vertices of a graph is called well covered weighting if the sum of the weights is the same for every maximal independent set. The set of weightings form a vector space. We consider the problems of finding the dimension of the space and what subgraphs are induced by the non-zero weighted vertices of the basis vectors. We completely answer these questions for several families of graphs and also show that the characteristic of the field affects the dimension. Along the way, anti-well-covered graphs - graphs whose sum is zero - are introduced and a step toward a structural characterization of well-covered graphs with no 4-cycles is taken.

Date received: April 18, 2001