Interval greedoids and families of local maximum stable sets of graphs

Details Interval greedoids and families of local maximum stable sets of graphs Interval greedoids and families of local maximum stable sets of graphs

2008-11-25

arxiv.org/abs/0811.4089v1

Mathematics

Combinatorics

13 pages, 11 figures

Scientific paper

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G, if S is a maximum stable set of the subgraph induced by its closed neighborhood. Nemhauser and Trotter Jr. proved in 1975 that any local maximum stable set is a subset of a maximum stable set of G. In 2002 we showed that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, while the family of all local maximum stable sets is a greedoid, were analyzed in 2004, 2007, and 2008, respectively. In this paper we demonstrate that if the family of all local maximum stable sets of the graph satisfies the accessibility property, then it is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids.

Affiliated with

Also associated with

No associations

Rating

Interval greedoids and families of local maximum stable sets of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Interval greedoids and families of local maximum stable sets of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval greedoids and families of local maximum stable sets of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-304533