| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649942 | Discrete Mathematics | 2008 | 8 Pages |
Abstract
Matching extendability is significant in graph theory and its applications. The basic notion in this direction is nn-extendability introduced by Plummer in 1980. Motivated by the different natures of bipartite matchings and non-bipartite matchings, this paper investigates bipartite-matching extendable (BM-extendable) graphs. A graph GG is said to be BM-extendable if every matching MM which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching. Our main results are showing that the recognition of BM-extendable graphs is co-NP-complete and characterizing some classes of BM-extendable graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Xiumei Wang, Zhenkun Zhang, Yixun Lin,