Well-covered Graphs and Greedoids

Levit, V. and Mandrescu, E.

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)