On local maximum stable set greedoids

A maximum stable set   in a graph GG is a stable set of maximum cardinality. SS is a local maximum stable set   of GG, and we write S∈Ψ(G)S∈Ψ(G), if SS is a maximum stable set of the subgraph induced by S∪N(S)S∪N(S), where N(S)N(S) is the neighborhood of SS. A greedoid (V,F)(V,F) is called a local maximum stable set greedoid   if there exists a graph G=(V,E)G=(V,E) such that F=Ψ(G)F=Ψ(G).Nemhauser and Trotter Jr. (1975) [29], proved that any S∈Ψ(G)S∈Ψ(G) is a subset of a maximum stable set of GG. In Levit and Mandrescu (2002) [19] we have shown that the family Ψ(T)Ψ(T) of a forest TT forms a greedoid on its vertex set. The cases where GG is bipartite, triangle-free, well-covered, unicycle, while Ψ(G)Ψ(G) is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) [20], [21], [22], [18] and [25], respectively.In this paper, we demonstrate that if the family Ψ(G)Ψ(G) satisfies the accessibility property, then, first, Ψ(G)Ψ(G) is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by GG, is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids. For these cases, some polynomial recognition algorithms are suggested.