2008/11/25 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05B35 (Primary) #05C69 #51D10 #90C27 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Peroxisome Proliferator-Activated Receptors #cs.DM #math.CO #msc:05B35 #msc:05C69 #msc:51D10 #msc:90C27
paper · pdf · doi:10.48550/arxiv.0811.4089
13 pages, 11 figures
arxiv created 2008/11/25 · openalex publication_date 2008/11/25 · arxiv updated 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.