2011/02/06 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1
Computer Science · Mathematics · #05B35 (Primary) #05C69 #05C70 (Secondary) #51D10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05B35 #acm:05C69 #acm:05C70 #acm:51D10 #cs.DM #math.CO #msc:05B35 #msc:05C69 #msc:05C70 #msc:51D10
paper · pdf · doi:10.48550/arxiv.1102.1142
12 pages, 12 figures
arxiv created 2011/02/06 · arxiv updated 2011/02/08
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.