关于图的(g,f)-因子分解

(g,f)-FACTORIZATIONS OF GRAPHS

讨论了图的(g,f)-因子分解问题,给出了一个图G是(g,f)-可因子化的若干充分条件。

The problem of (g,f)-factori-zations of graphs is discussed, and some sufficient conditions for a graph to be (g,f)-factorable are given. The following two Theorems are proved:Theorem 1. Let G be a (3mg(x)-2, 3mf(x)+2)-graph, where g(x) and f(x) are integer-valued functions defined on V(G) with f(x)≥g(x)≥1 and m≥2. Then G is(3g-1, 3f+1)-factorable if one of the following conditions is satisfied.(1) m even, G is connected, and the vertex set {x:3mg(x)-2<d_G(x)<3mf(x)+2} is not empty;(2) m odd, and there is at most one vertex in G of either 3mg(x)-2 or 3mf(x)+2.Theorem 2. Let s≥o and t≥1 be two integers, and g(x), f(x) be integer-valued functions on V(G) with f(x)≥g(x)≥1. If G is a ((18g(x)-2)t+3sg(x), (18f(x)+2)t+3sf(x))-graph, then G is (3g-1, 3f+1)-factorable.