二分图中度条件与[a,b]-覆盖图

Degree conditions and [a,b]-covered graphs in bipartite graphs

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g<f.图G的一个(g,f)-因子是G的一个支撑子图F,使得对任意的x∈V(G),有g(x)≤dF(x)≤f(x).如果过图G的任何两条边都有一个(g,f)-因子,则称图G是一个(g,f)-覆盖图.设G=(X,Y;E)为二分图,其中|x|=|y|=n,本文证明了:若δ(G)≥a+b+n-2bn-1,或n≥(a+b)2-a+b且δ(G)≥an+1,则G是[a,b]-覆盖图.

Let g be a graph with vertex set V(G) and edge set E(G),and let g and f be two integer-valued functions defined on V(G), such that g<f for every x∈V(G). A (g,f)-factor of G is a spanning subgraph F of G, such that g(x)≤d_F(x)≤f(x) for every x∈V(G). A graph G is called a (g,f)-covered graph if every two edges belong to a (g,f)-factor. Let G=(X,Y;E) be a balance bipartite graph, where X=Y=n.In this paper, it is proved that, if δ(G)≥a+b+n-2bn-1, or δ(G)≥an+1a+b and n≥(a+b)2b-a+bb, then G is a [a,b]-covered graph .