CAJ | 학술논문

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.
설G시함유완미필배적간단도.칭도G시우필배가확적(BM-가확적),여과G적매일개도출자도시우도적필배M도가이확충위일개완미필배.겁도문제시도론적핵심문제지일.본문장각화겁대우필배불가확도,우도도류화완전다부도도류중적겁대우필배가확도.
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 κ-partite graphs with κ≥2.