Orthogonal (g, f)-factorizations in networks

Let G = (V, E) be a graph and let g and f be two integer-valued functions d efined on V such that k less than or equal to g(x) less than or equal to f( x) for all x is an element of V. Let H-1, H-2, ..., H-k be subgraphs of G s uch that \ E(H-i)\ = m, 1 less than or equal to i less than or equal to k, and V(H-i) boolean AND V(H-j) = 0 when i not equal j. In this paper, it is proved that every (mg + m - 1, mf - m + 1)-graph G has a (g, f)-factorizati on orthogonal to H-i for i = 1, 2, ..., k and shown that there are polynomi al-time algorithms to find the desired (g, f)-factorizations. (C) 2000 John Wiley & Sons, Inc.