LOCAL-STRUCTURE WHEN ALL MAXIMAL INDEPENDENT SETS HAVE EQUAL WEIGHT

In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they all have the same size or the same parity. Both of these quest ions may be formulated by weighting the points with elements of an abe lian group, and asking whether all maximal independent sets have equal weight. If a set is independent precisely when its elements are pairw ise independent, a graph can be used as a model. The question then bec omes whether a graph, with its vertices weighted by elements of an abe lian group, is well-covered, i.e., has all maximal independent sets of vertices with equal weight. This problem is known to be co-NP-complet e in general. We show that whether a graph is well-covered or not depe nds on its local structure. Based on this, we develop an algorithm to recognize well-covered graphs. For graphs with n vertices and maximum degree Delta, it runs in linear time if Delta is bounded by a constant , and in polynomial time if Delta = O((3)root log n). We mention vario us applications to areas including hypergraph matchings and radius k i ndependent sets. We extend our results to the problem of determining w hether a graph has a weighting which makes it well-covered.