Critical sets, crowns and local maximum independent sets.

A set S ⊆ V (G) is independent if no two vertices from S are adjacent, and by Ind (G) we mean the set of all independent sets of G. A set A ∈ Ind (G) is critical (and we write A ∈ C r i t I n d e p (G) ) if A - N (A) = max { I - N (I) : I ∈ Ind (G) } [37], where N(I) denotes the neighborhood of I. If S ∈ Ind (G) and there is a matching from N(S) into S, then S is a crown [1], and we write S ∈ C r o w n (G) . Let Ψ (G) be the family of all local maximum independent sets of graph G, i.e., S ∈ Ψ (G) if S is a maximum independent set in the subgraph induced by S ∪ N (S) [22]. In this paper, we present some classes of graphs where the families CritIndep(G), Crown(G), and Ψ (G) coincide and form greedoids or even more general set systems that we call augmentoids. [ABSTRACT FROM AUTHOR]