A new result on orthogonal factorizations in networks

Abstract

Let m, n, r, ? and ki (1 ? i ? m) be positive integers satisfying 1 ? n ? m and k1 ? k2 ???? ? km ? (3? ? 1)r ? 1. Let G be a graph, and let H be an m?-subgraph of G and F = {F1, F2,???, Fm} be a (g, f)- factorization of G. If for any partition {A1,A2,???,Am} of E(H) with |Ai| = ?, G admits a (1, f )-factorization F = {F1, F2,???, Fm} satisfying Ai ? E(Fi) for 1 ? i ? m, then we say that F is randomly ?-orthogonal to H. Let H1,H2,???,Hr be r vertex-disjoint n?-subgraphs of a [0, k1 + k2 +???+ km ? n + 1]-graph G. In this paper, it is proved that a [0, k1 + k2 +??? + km ? n + 1]-graph G contains a subgraph R such that R possesses a [0, ki]n1-factorization randomly ?-orthogonal to every Hi, 1 ? i ? r.

Topics & Concepts