کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419430 | 683803 | 2012 | 8 صفحه PDF | دانلود رایگان |

A maximum stable set in a graph GG is a stable set of maximum cardinality. The set SS is called a local maximum stable set of GG, and we write S∈Ψ(G)S∈Ψ(G), if SS is a maximum stable set of the subgraph induced by the closed neighborhood of SS. A greedoid (V,F)(V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E)G=(V,E) such that F=Ψ(G)F=Ψ(G).Nemhauser and Trotter Jr. (1975) [28] proved that any S∈Ψ(G)S∈Ψ(G) is a subset of a maximum stable set of GG. In Levit and Mandrescu (2002) [16] we showed that the family Ψ(T)Ψ(T) of a forest TT forms a greedoid on its vertex set. The cases where GG is bipartite, triangle-free, and well-covered while Ψ(G)Ψ(G) is a greedoid were analyzed in Levit and Mandrescu (2004) [18], Levit and Mandrescu (2007) [20], and Levit and Mandrescu (2008) [23], respectively.In this paper we demonstrate that if GG is a very well-covered graph, then the family Ψ(G)Ψ(G) is a greedoid if and only if GG has a unique perfect matching.
Journal: Discrete Applied Mathematics - Volume 160, Issue 12, August 2012, Pages 1864–1871