Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids

Details Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids

2000-11-21

arxiv.org/abs/math/0011156v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bipartite graphs with uniquely restricted maximum matchings and their corresponding greedoids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-176723