A new result on orthogonal factorizations in networks

Abstract

Let $m$, $n$, $r$, $\lambda$ and $k_i$ $(1\leq i\leq m)$ be positive integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq(3\lambda-1)r-1$. Let $G$ be a graph, and let $H$ be an $m\lambda$-subgraph of $G$ and $\mathcal{F}=\{F_1,F_2,\cdots,F_m\}$ be a $(g,f)$-factorization of $G$. If for any partition $\{A_1,A_2,\cdots,A_m\}$ of $E(H)$ with $|A_i|=\lambda$, $G$ admits a $(g,f)$-factorization $\mathcal{F}=\{F_1,F_2,\cdots,F_m\}$ satisfying $A_i\subseteq E(F_i)$ for $1\leq i\leq m$, then we say that $\mathcal{F}$ is randomly $\lambda$-orthogonal to $H$. Let $H_1,H_2,\cdots,H_r$ be $r$ vertex-disjoint $n\lambda$-subgraphs of a $[0,k_1+k_2+\cdots+k_m-n+1]$-graph $G$.
In this paper, it is proved that a $[0,k_1+k_2+\cdots+k_m-n+1]$-graph $G$ contains a subgraph $R$ such that $R$ possesses a
$[0,k_i]_1^{n}$-factorization randomly $\lambda$-orthogonal to every $H_i$, $1\leq i\leq r$.