Orthogonal \((g, f)\)-Factorizations in Graphs

Abstract

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\), and let \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) such that \(0 \leq 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 \({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 one edge in common with \(H\), we say that \({F}\) is orthogonal to \(H\). In this paper, it is proved that every \((mg+k-1, mf-k+1)\)-graph contains a subgraph \( {R}\) such that \( {R}\) has a \((g, f)\)-factorization orthogonal to any given subgraph with \(k\) edges of \(G\) if \(f(x) > g(x) \geq 0\) for each \(x \in V(G)\) and \(1 \leq k \leq m\), where \(m\) and \(k\) are two positive integers.