二分图中k-因子存在的两个充分条件

TWO SUFFICIENT CONDITIONS FOR THE EXISTENCE OF k-FACTORS IN BIPARTITE GRAPHS

设G =(X ,Y ;E)为二分图 ,其中｜X｜ =｜Y｜=n为整数 .证明了 :若δ(G) >n+ 2k-2 kn+ 1 ,或b′(G) >(n-1 ) /[2 ( kn+ 1 -k) ] ,其中b′(G)为与联结数相类似的一种参数 ,则G有k 因子 .并且将说明 ,当k<n≤4k且kn+ 1为完全平方数时 。

Suppose G=(X,Y;E)is a bipartite graph where |X|=|Y|=n. In this paper,we prove that if δ(G)>n+2k-2kn+1,or b′(G)>(n-1)/kn+1-k)]where b′(G) is an invariant analogous with binding numer,then G has k-factors.We also show that if k<n≤4k and where b′(G) is an invariant analogous with binding numer,then G has k-factors.We also show that if k<n≤4k and kn+1 is an integer,then these two conditions are sharp.