A new Greedoid: the family of local maximum stable sets of a forest ?
A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set if it is a maximum stable of the subgraph of G spanned by S?N(S), where N(S) is the neighborhood of S. One theorem of Nemhauser and Trotter Jr. (Math. Programming 8 (1975) 232248), working as a useful sufficient local optimality condition for the weighted maximum stable set problem, ensures that any local maximum stable set of G can be enlarged to a maximum stable set of G. In this paper we demonstrate that an inverse assertion is true for forests. Namely, we show that for any non-empty local maximum stable set S of a forest T there exists a local maximum stable set S1 of T, such that S1?S and |S1|=|S|?1. Moreover, as a further strengthening of both the theorem of Nemhauser and Trotter Jr. and its inverse, we prove that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set.
05c05 05c12 05c70 05c75