Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs

Details Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs

2011-02-06

arxiv.org/abs/1102.1142v1

Computer Science

Discrete Mathematics

12 pages, 12 figures

Scientific paper

A maximum stable set in a graph G is a stable set of maximum cardinality. S is called a local maximum stable set of G if S is a maximum stable set of the subgraph induced by the closed neighborhood of S. A greedoid (V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E) such that its family of local maximum stable sets coinsides with (V,F). It has been shown that the family local maximum stable sets of a forest T forms a greedoid on its vertex set. In this paper we demonstrate that if G is a very well-covered graph, then its family of local maximum stable sets is a greedoid if and only if G has a unique perfect matching.

Affiliated with

Also associated with

No associations

Rating

Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered 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 Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Maximum Stable Sets Greedoids Stemmed from Very Well-Covered Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-506044