Orthogonal (<TOGGLE>g, f</TOGGLE>)-factorizations in networks

Let G = (V, E) be a graph and let g and f be two integer-valued functions defined on V such that k ≤ g(x) ≤ f(x) for all x ∈ V. Let H<INF>1</INF>, H<INF>2</INF>, …, H<INF>k</INF> be subgraphs of G such that |E(H<INF>i</INF>)| = m, 1 ≤ i ≤ k, and V(H<INF>i</INF>) ∩ V(H<INF>j</INF>) = 0 when i ≠ j. In this paper, it is proved that every (mg + m − 1, mf − m + 1)-graph G has a (g, f)-factorization orthogonal to H<INF>i</INF> for i = 1, 2, …, k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations. © 2000 John Wiley & Sons, Inc.