Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
✍ Scribed by Vadim E. Levit; Eugen Mandrescu
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 233 KB
- Volume
- 132
- Category
- Article
- ISSN
- 0166-218X
No coin nor oath required. For personal study only.
✦ Synopsis
A maximum stable set in a graph G is a stable set of maximum size. S is a local maximum stable set of G, and we write S ∈ (G), if S is a maximum stable set of the subgraph spanned by S ∪ N (S), where N (S) is the neighborhood of S. A matching M is uniquely restricted if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself. Nemhauser and Trotter Jr. (Math. Programming 8(1975) 232-248), proved that any S ∈ (G) is a subset of a maximum stable set of G. In Levit and Mandrescu (Discrete Appl. Math., 124 (2002) 91-101) we have shown that the family (T ) of a forest T forms a greedoid on its vertex set. In this paper, we demonstrate that for a bipartite graph G, (G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted.