关于在K_(1,n)-free图中存在正则因子度条件的推广(英文)

More on the degree condition for the existence ofregular factors in K_(1,n)-free graphs

图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1)+1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a+1)b+1「b+a(n-1)2(n-1) -n-1b「b+a(n-1)2(n-1) 2+n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。

A graph is called K_(1,n)-free if it contains no K_(1,n) as an induced subgraph. Let G be a graph with vertex set (V(G)), and let g and f be two integer-valued functions defined on V(G) such that g(x)f(x) for all (x∈V(G)). Let a =max {g(x)｜x∈V(G)}, b=min {f(x)｜x∈V(G)}, and b, a2, nb/(a-1)(+1)(if there exists a vertex v∈V(G) such that f(v)≡1 (mod 2), bn-1). We prove that every K_(1,n)-free connected graph G with ∑x∈V(G) f(x) even has a (g, f)-factor if its minimum degree is at least?-n-1b(n-1)?~2+n-3.This result is the generalization for the existence theorem of regular factors in K_(1,n)-free graphs, which is due to K. Ota and T. Tokuda (J. Graph Theory. 1996, 22:59-64).