Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids
| dc.creator | Levit, Vadim E. | |
| dc.creator | Mandrescu, Eugen | |
| dc.date | 2000-11-21 | |
| dc.date.accessioned | 2026-07-07T04:38:43Z | |
| dc.date.available | 2026-07-07T04:38:43Z | |
| dc.description | A maximum stable set in a graph G is a stable set of maximum size. 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. A matching M is uniquely restricted if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself. 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 one of our previous papers it is proven that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. In this paper we obtain a generalization of this assertion claiming that the family of all local maximum stable sets of a bipartite graph G is a greedoid if and only if all maximum matchings of G are uniquely restricted. | |
| dc.identifier | https://arxiv.org/abs/math/0011156 | |
| dc.identifier | http://arxiv.org/abs/math/0011156 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/60392 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C70, 05C69, 51D10 (Primary) 90C10 (Secondary) | |
| dc.title | Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids | |
| dc.type | text |