Decomposition of graphs into (g, f)-factors

Abstract

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x) ≤ degG(x) ≤ f(x) for each x ∈ V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g ,f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l = m (mod 4) and 0 ≤ l ≤ 3. If G is an (mg + 2 [m/4] + l, mf - 2 [m/4] - l)-graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. © Springer-Verlag 2000.