Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (1): 23-30.

• Original Articles • Previous Articles     Next Articles

Extremal Graphs about Bipartite Matching Extendability

WANG Xiu-Mei, SHANG Wei-苹, LIN Yi-Xun   

  • Online:2010-03-15 Published:2010-03-15

Abstract: Let $G$ be a simple  graph containing a perfect matching.  $G$ is said to be bipartite matching extendable (BM-extendable) if every matching $M$ whose induced subgraph is a bipartite graph extends to a perfect matching. Extremal graph problems are at the core  of graph theory. In this paper, we characterize maximally BM-unextendable graphs, maximally BM-extendable graphs in the class of complete $k$-partite graphs with $k\geq 2$.