Smallest Close to Regular Bipartite Graphs without an Almost Perfect Matching

作     者：Lutz VOLKMANN Axel ZINGSEM 

作者机构：Lehrstuhl Ⅱ für Mathematik RWTH Aachen University 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2010年第26卷第8期

页      面：1403-1412页

核心收录：

学科分类：07[理学] 08[工学] 080203[工学-机械设计及理论] 070104[理学-应用数学] 0802[工学-机械工程] 0701[理学-数学] 

主　　题：Almost perfect matching bipartite graph close to regular graph 

摘      要：A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥*** will demonstrate that the given bounds on the order of G are the best possible.