On local maximum stable set greedoids

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G , and we write S ∈ Ψ ( G ) , if S is a maximum stable set of the subgraph induced by S ∪ N ( S ) , where N ( S ) is the neighborhood of S . A greedoid ( V , F ) is called a local maximum stable set greedoid if there exists a graph G = ( V , E ) such that F = Ψ ( G ) . ser and Trotter Jr. (1975) [29], proved that any S ∈ Ψ ( G ) is a subset of a maximum stable set of G . In Levit and Mandrescu (2002) [19] we have shown that the family Ψ ( T ) of a forest T forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, unicycle, while Ψ ( G ) is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) [20–22,18,25], respectively. s paper, we demonstrate that if the family Ψ ( G ) satisfies the accessibility property, then, first, Ψ ( G ) is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by G , 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.