Smallest close to regular bipartite graphs without an almost perfect matching

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
Keywords:	Almost perfect matching   bipartite graph   close to regular graph
本文献已被 维普 SpringerLink 等数据库收录！