Cn×P2的2-偶匹配可扩性

摘要

Let G be a connected graph containing a perfect matching.G is said to be bipartite matching extendable if every matching M of G whose induced subgraph is a bipartite matching extends to a perfect matching of G.To further study the bipartite matching extendable graphs,we consider the bipartite matching number of G,denoted by BM(G),is the number of edges of a maimum bipartite matching of G.In this paper we prove that Cn×P2 is 2-Bipartite matching extendable.%称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V(M)]是偶图.称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中,为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM(G).我们证明了Cn×P2是2-偶匹配可扩的.