Randomly \(r\)-Orthogonal \((0, f)\)-Factorizations of Bipartite \((0,mf – (m – 1)r)\)-Graphs

Abstract

Let \(G = (X, Y, E(G))\) be a bipartite graph with vertex set \(V(G) = X ! Y\) and edge set \(E(G)\), and let \(g, f\) be two nonnegative integer-valued functions defined on \(V(G)\) such that \(g(x) \leq f(x)\) for each \(x \in V(G)\). A \((g, f)\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(g(x) \leq d_F(x) \leq f(x)\) for each \(x \in V(F)\); a \((g, f)\)-factorization of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g, f)\)-factors. Let \(\mathcal{F} = \{F_1, F_2, \ldots, F_m\}\) be a factorization of \(G\) and \(H\) be a subgraph of \(G\) with \(m\) edges. If \(F_i\), \(1 \leq i \leq m\), has exactly \(r\) edges in common with \(H\), we say that \(F_i\) is \(r\)-orthogonal to \(H\). In this paper, it is proved that every bipartite \((0, mf-(m-1)r)\)-graph has \((0, f)\)-factorizations randomly \(r\)-orthogonal to any given subgraph with \(m\) edges if \(2r \leq f(x)\) for any \(x \in V(G)\).