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

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 $\ge 4$, then the family $\Psi (G)$ is a greedoid if and only if $G$ has a unique perfect matching.

arXiv comment7 pages, 5 figures