Publication:1850118

DOI10.1016/S0166-218X(01)00332-8zbMATH Open1007.05083arXivmath/9912222OpenAlexW2078342963MaRDI QIDQ1850118FDOQ1850118

Eugen Mandrescu, Vadim E. Levit

Publication date: 2 December 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/math/9912222

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• The structure and maximum number of maximum independent sets in trees
• Greedoids
• Reducing the adjacency matrix of a tree
• Graphs whose vertex independence number is unaffected by single edge addition or deletion

Cited In (14)

• VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS
• Unicycle graphs and uniquely restricted maximum matchings
• On König-Egerváry collections of maximum critical independent sets
• The Clique Corona Operation and Greedoids
• On local maximum stable set greedoids
• Critical sets, crowns and local maximum independent sets
• Graph operations that are good for greedoids
• Local maximum stable set greedoids stemming from very well-covered graphs
• On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph
• Critical independent sets and König-Egerváry graphs
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Crowns in bipartite graphs
• On unicyclic graphs with uniquely restricted maximum matchings
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

This page was built for publication: A new greedoid: The family of local maximum stable sets of a forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850118)