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). Nemhauser 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) [2022,18,25], respectively. In this 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.