Critical sets, crowns and local maximum independent sets (Q2149605)

Let \(G\) be a graph with vertex set \(V(G)\); denote the neighbors of \(U \subseteq V(G)\) by \(N(U)\). Three types of independent sets are studied. An independent set \(I\) is critical independent if \(|I|-|N(I)| \geq |J| - |N(J)|\) for any independent set \(J\); it is a crown if there exists a matching from \(N(I)\) to \(I\); and is local maximum independent if it is of maximum size in the subgraph induced by \(I \cup N(I)\). The authors study the interplay between these concepts and also König-Evergáry graphs. They show, in particular, that a critical independent set is a crown, which is in turn, local maximum independent. Generalizing a greedoid, they coin the useful concept of an augmentoid. An augmentoid consists of a non-empty family \(\mathcal F\) of subsets of a set \(E\) satisfying the following: for \(X,Y \in \mathcal F\), there exists \(A \subseteq X - Y\) and \(B \subseteq Y - X\) so that \(Y \cup A, X \cup B \in \mathcal F\) and \(|Y \cup A | = |X \cup B|\). Various examples of augmentoids are given, among them are the collection of crowns and of critical independent sets in the set \(V(G)\). Augmentoids enjoy the property that each of its elements can be enlarged to one which is maximal by inclusion. This concept is used to prove a number of new though not unexpected properties of the independent sets studied in the paper. Various relationships between these concepts and König-Evergáry graphs are exposed. The proofs are straightforward. The concept of an augmentoid appears primed for further study.