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 H1, H2,⋯, Hk be subgraphs of G such that \E(Hi)\ = m, 1 ≤ i ≤ k, and V(Hi) ∩ V(Wj) = ø 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 Hi for i = 1, 2, ⋯, k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations.
|Number of pages||5|
|Publication status||Published - Jul 2000|
Scopus Subject Areas
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications
- orthogonal factorization