2010/08/17 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Neuroscience · #05C69 (Primary) 52B40 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Nuclear Receptors and Signaling #Peroxisome Proliferator-Activated Receptors #acm:05C69 #acm:52B40 #cs.DM #math.CO #msc:05C69 #msc:52B40
paper · pdf · doi:10.48550/arxiv.1008.2897
7 pages, 5 figures
arxiv created 2010/08/17 · openalex publication_date 2010/08/17 · arxiv updated 2010/08/18 · openalex created_date 2025/10/24 · 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, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph induced by S∪ N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter Jr. (1975), proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In (Levit & Mandrescu, 2002) we have shown that the family Ψ(T) of a forest T forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, while Ψ(G) is a greedoid, were analyzed in (Levit & Mandrescu, 2002),(Levit & Mandrescu, 2004),(Levit & Mandrescu, 2007), respectively. In this paper we demonstrate that if G is a very well-covered graph of girth ≥4, then the family Ψ(G) is a greedoid if and only if G has a unique perfect matching.