关于极大二部匹配可扩图

On maximal bipartite matching extendable graphs

若简单图G的每一个二部匹配都可增扩为G的一个完美匹配,则称图G是二部匹配可扩图(简称BM-可扩图)。BM-可扩图广泛地存在于相对稠密的图类之中。讨论树梯图、加强树梯图和正则加强树梯图等图类,并在树梯图图类中确定了正则加强树梯图是加强树梯图中的极大BM-可扩图的刻画。该结论与Wang Xiu-mei一起给出了三类极大BM-可扩图的完全刻画。

If every bipartite match in a simple graph G can be expanded to one of its perfect match, G is called a bipartite-matching extendable graph （ simply denoted by BM-extendable graph）. In the family of dense graphs, there are many BM-extendable graphs. Families of tree-ladders, stronger tree-ladders and regular stronger tree-ladders are intradueed. It is shown that in the family of stronger tree-ladders, the only maximal BM-extendable graphs are regular stronger tree-ladders. This together with those Wang Xiu-mei＇ s paper give a complete characterization of maximal BM-extendable graphs in three families of graphs.