G is a well-covered graph provided all its maximal
stable sets are of the same size. S
is a local maximum stable set of G, and we denote
by 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.
In 2002 we have proved that \Psi(G) is a greedoid for
every forest G. The bipartite graphs and the triangle-
free graphs, whose families of local maximum stable
sets form greedoids were characterized by Levit and
Mandrescu.
In this paper we demonstrate that if a graph G has
a perfect matching consisting of only pendant edges,
then \Psi(G) forms a greedoid on its vertex set. In
particular, we infer that \Psi(G) forms a greedoid for
every well-covered graph G of girth at least 6, non-
isomorphic to C_7.
Cite as: Levit, V. and Mandrescu, E. (2008). Well-covered Graphs and Greedoids. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 87-91.
(from crpit.com)
(local if available)