English

运筹学学报 ›› 2010, Vol. 14 ›› Issue (1): 23-30.

• 运筹学 • 上一篇    下一篇

偶匹配可扩性的极图问题

王秀梅, 尚卫苹, 林诒勋   

  • 出版日期:2010-03-15 发布日期:2010-03-15

Extremal Graphs about Bipartite Matching Extendability

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

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

被引次数

2

摘要： 设G是含有完美匹配的简单图. 称图G是偶匹配可扩的(BM-可扩的), 如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配. 极图问题是图论的核心问题之一. 本文将刻画极大偶匹配不可扩图, 偶图图类和完全多部图图类中的极大偶匹配可扩图.  

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$.