Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids

A $\mathit{\text{maximum}}\mathit{\text{stable}}\mathit{\text{set}}$ in a graph $G$ is a stable set of maximum cardinality. $S$ is a $\mathit{\text{local}}\mathit{\text{maximum}}\mathit{\text{stable}}\mathit{\text{set}}$ of $G$, and we write $S\in \mathrm{\Psi }(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup N(S)$,where$N(S)$istheneighborhoodof$S$. Nemhauser and Trotter Jr. (1975), proved that any $S\in \mathrm{\Psi }(G)$ is a subset of a maximum stable set of $G$. In (Levit & Mandrescu, 2002) we have shown that the family $\mathrm{\Psi }(T)$ of a forest $T$ forms a greedoid on its vertex set. The cases where $G$ is bipartite, triangle-free, well-covered, while $\mathrm{\Psi }(G)$ is a greedoid, were analyzed in (Levit & Mandrescu, 2002),(Levit & Mandrescu, 2004),(Levit & Mandrescu, 2007), respectively. In this paper we demonstrate that if $G$ is a very well-covered graph of girth $\ge 4$, then the family $\mathrm{\Psi }(G)$ is a greedoid if and only if $G$ has a unique perfect matching.