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

link: http://arxiv.org/abs/1008.2897
Abstract

A \textit{maximum stable set} in a graph $G$ is a stable set of maximum
cardinality. $S$ is a \textit{local maximum stable set} of $G$, and we write
$S\in\Psi(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup
N(S)$, where $N(S)$ is the neighborhood of $S$. Nemhauser and Trotter Jr.
(1975), proved that any $S\in\Psi(G)$ is a subset of a maximum stable set of
$G$. In (Levit & Mandrescu, 2002) we have shown that the family $\Psi(T)$ of a
forest $T$ forms a greedoid on its vertex set. The cases where $G$ is
bipartite, triangle-free, well-covered, while $\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 $\geq4$, then the family $\Psi(G)$ is a
greedoid if and only if $G$ has a unique perfect matching.