1999/12/29 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Computer Science · Mathematics · #05C05 #05C69 (Primary) 05B35 #90C10 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods #math.CO #msc:05B35 #msc:05C05 #msc:05C69 #msc:90C10
paper · pdf · doi:10.48550/arxiv.math/9912222
A preliminary version of this paper has been presented at DIMACS-RUTCOR Workshop DO'99: Discrete Optimization '99, July 1999, Rutgers University, USA; 10 pages, 9 figures
arxiv created 1999/12/29 · openalex publication_date 1999/12/29 · arxiv updated 2009/11/30 · 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 if it is a maximum stable set of the subgraph of G spanned by the union of S and N(S), where N(S) is the neighborhood of S. One theorem of Nemhauser and Trotter Jr., working as a useful sufficient local optimality condition for the weighted maximum stable set problem, ensures that any local maximum stable set of G can be enlarged to a maximum stable set of G. In this paper we demonstrate that an inverse assertion is true for forests. Namely, we show that for any non-empty local maximum stable set S of a forest T there exists a local maximum stable set S1 of T, such that S1 is included in S and |S1| = |S| - 1. Moreover, as a further strengthening of both the theorem of Nemhauser and Trotter Jr. and its inverse, we prove that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set.