关于在K1,n-free图中存在正则因子度条件的推广

图被称为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图中存在正则因子度条件的推广。

More on the degree condition for the existence of regular factors in K1,n-free graphs

A graph is called K1,n-free if it contains no K1,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 K1,n-free connected graph G with ∑x∈V(G) f(x) even has a (g, f)-factor if its minimum degree is at leastThis result is the generalization for the existence theorem of regular factors in K1,n-free graphs, which is due to K. Ota and T. Tokuda (J. Graph Theory. 1996, 22:59-64).