The existence of subdigraphs with orthogonal factorizations in digraphs

1.   Introduction

Many real-world networks can conveniently be simulated by graphs or networks. Examples include the World Wide Web with nodes modelling Web pages and links representing hyperlinks between Web pages, or a communication network with nodes simulating cities, and links modelling communication channels, an interconnection network with nodes representing processors and links simulating communication channels. The factors, fractional factors, factorizations and orthogonal factorizations in graphs or networks attracted a great deal of attention ^{[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]} due to their applications in network design, combinatorial design, the file transfer problems on computer networks, coding design, scheduling problems, and so on. The file transfer problem can be simulated as $(0, f)$-factorizations in a graph ^[18]. The design of a Room square with order $2n$ is equivalent to the orthogonal 1-factorization of $K_{2n}$ which is firstly posed by Horton ^[19]. The design of a pair of orthogonal Latin squares with order $n$ is related to two orthogonal 1-factorizations of $K_{n, n}$ which is firstly posed by Euler ^[20]. It is well-known that a network can be simulated by a graph. Vertices of the graph represent nodes of the network, and edges of the graph represent links between the nodes in the network. Henceforth, we replace network by the term graph.

In this article, we discuss finite directed graphs (digraphs) without loops or parallel arcs. Let $G$ be a digraph. We denote the vertex set and arc set of $G$ by $V(G)$ and $E(G)$, respectively. For $x\in V(G)$, we denote by $d^{-}_G(x)$ the indegree of $x$ in $G$, and by $d^{+}_G(x)$ denote the outdegree of $x$ in $G$. We use $xy$ to denote the arc with tail $x$ and head $y$. Let $g = (g^{-}, g^{+})$ and $f = (f^{-}, f^{+})$ be pairs of nonnegative integer-valued functions defined on $V(G)$ satisfying $g^{-}(x)\leq f^{-}(x)$ and $g^{+}(x)\leq f^{+}(x)$ for every $x\in V(G)$. A spanning subdigraph $F$ of a digraph $G$ is called a $(g, f)$-factor of $G$ if it satisfies $g^{-}(x)\leq d_F^{-}(x)\leq f^{-}(x)$ and $g^{+}(x)\leq d_F^{+}(x)\leq f^{+}(x)$ for all $x\in V(G)$. We call $G$ a $(g, f)$-digraph if $G$ itself is a $(g, f)$-factor. For convenience, we write $g\leq f$ if $g^{-}(x)\leq f^{-}(x)$ and $g^{+}(x)\leq f^{+}(x)$ for every $x\in V(G)$, and write $g\geq k$ if $\min\{g^{-}(x), g^{+}(x)\}\geq k$ for every $x\in V(G)$, and write $g = a$ if $g^{-}(x) = a$ and $g^{+}(x) = a$ for every $x\in V(G)$, where $a$ is a nonnegative integer. Furthermore, we shall write $mf+n$ for $(mf^{-}+n, mf^{+}+n)$. If $g(x) = a$ and $f(x) = b$ for any $x\in V(G)$, then we call a $(g, f)$-factor as an $[a, b]$-factor and a $(g, f)$-digraph as an $[a, b]$-digraph. If $E(G)$ can be decomposed into arc-disjoint $[0, k_1]$-factor $F_1$, $[0, k_2]$-factor $F_2$, $\cdots$, $[0, k_m]$-factor $F_m$, then we say $\mathcal{F} = \{F_1, F_2, \cdots, F_m\}$ is a $[0, k_i]_1^{m}$-factorization of a digraph $G$, where $k_i$ is a positive integer for $1\leq i\leq m$.

A subdigraph $H$ of a digraph $G$ is called an $m$-subdigraph if $H$ possesses $m$ arcs in total. Let $H$ be an $m$-subdigraph of $G$ and $\mathcal{F} = \{F_1, F_2, \cdots, F_m\}$ be a $[0, k_i]_1^{m}$-factorization of $G$. If $|E(H)\cap E(F_i)| = 1$ for $1\leq i\leq m$, then we say that $\mathcal{F}$ is orthogonal to $H$, namely, $\mathcal{F}$ is an orthogonal $[0, k_i]_1^{m}$-factorization of $G$. Similarly, we may define an orthogonal $(g, f)$-factorization of $G$.

Zhou and Sun ^[21,22] posed some sufficient conditions for graphs to admit $[1,2]$-factors with given properties. Zhou ^[23] studied the existence of $[1,2]$-factors with given properties. Kouider and Lonc ^[24] derived some results on $[a, b]$-factors in graphs. Yan, Pan, Wong and Tokuda ^[25] investigated $(g, f)$-factorizations of graphs. Alspach, Heinrich and Liu ^[14] put forward the following problem: Given a subetaaph $H$ of $G$, does there exist a factorization $\mathcal{F}$ of $G$ of certain type orthogonal to $H$? Liu ^[26] demonstrated that every $(mg+m-1, mf-m+1)$-graph admits a $(g, f)$-factorization orthogonal to an $m$-matching. Lam, Liu, Li and Shiu ^[27] justified that every $(mg+m-1, mf-m+1)$-graph admits a $(g, f)$-factorization orthogonal to $k$ given vertex-disjoint $m$-subetaaphs. Feng and Liu ^[28] claimed that every $[0, k_1+k_2+\cdots+k_m-m+1]$-graph possesses a $[0, k_i]_1^{m}$-factorization orthogonal to any given $m$-subetaaph. Wang ^[29] verified the existence of subetaaphs with orthogonal $[0, k_i]_1^{n}$-factorizations in $[0, k_1+k_2+\cdots+k_m-n+1]$-graphs. Liu ^[30] investigated orthogonal $(g, f)$-factorizations of $(mg+m-1, mf-m+1)$-digraphs. Wang ^[31] claimed that every $(mg+k-1, mf-k+1)$-digraph includes a subdigraph $R$ such that $R$ admits a $(g, f)$-factorization orthogonal to $n$ arc-disjoint $k$-subdigraphs. Zhou and Bian ^[32] verified that every $(mg+(k-1)r, mf-(k-1)r)$-digraph includes a sundigraph $R$ such that $R$ admits a $(g, f)$-factorization orthogonal to $r$ vertex-disjoint $k$-subdigraphs. Zhou, Sun and Xu ^[33] demonstrated that every $(0, mf-m+1)$-digraph possesses a $(0, f)$-factorization orthogonal to $k$ vertex-disjoint $m$-subdigraphs.

In this article, we study the following problem: For given $r$ vertex-disjoint $n$-subdigraphs $H_1, H_2, \cdots, H_r$ of a digraph $G$, does $G$ admit factorization orthogonal to every $H_i$ ($i = 1, 2, \cdots, r$)? Furthermore, we verify the following theorem, which partly solves the above problem.

Theorem 1. Let $G$ be a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph, and let $H_1, H_2, \cdots, H_r$ be $r$ vertex-disjoint $n$-subdigraphs of $G$, where $m, n, r$ and $k_i$ ($1\leq i\leq m$) are positive integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$. Then there exists a subdigraph $R$ of $G$ such that $R$ possesses a $[0, k_i]_1^{n}$-factorization orthogonal to every $H_i$ for $1\leq i\leq r$.

Obviously, we admit the following result by setting $r = 1$ in Theorem 1.

Corollary 1. Let $G$ be a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph, and let $H$ be an $n$-subdigraphs of $G$, where $m, n$ and $k_i$ ($1\leq i\leq m$) are positive integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq2$. Then there exists a subdigraph $R$ of $G$ such that $R$ possesses a $[0, k_i]_1^{n}$-factorization orthogonal to $H$.

2.   Preliminary lemmas

Let $G$ be a digraph. For any two vertex subsets $S$ and $T$ of $G$, we write $E_G(S, T) = \{xy:xy\in E(G), x\in S, y\in T\}$, and let $e_G(S, T) = |E_G(S, T)|$. Let $\varphi$ be a function defined on $V(G)$. We write $\varphi(S) = \sum\limits_{x\in S}\varphi(x)$ and $\varphi(\emptyset) = 0$. Define

and

Let $S$ and $T$ be two vertex subsets of $G$, and $E_1$ and $E_2$ be two disjoint subsets of $E(G)$. Put

for $i = 1, 2$, and set

For simplicity, $\alpha_S(S, T; E_1)$, $\beta_T(S, T; E_2)$, $\alpha_T(S, T; E_1)$ and $\beta_S(S, T; E_2)$ are written as $\alpha_S$, $\beta_T$, $\alpha_T$ and $\beta_S$ under without ambiguity.

Liu ^[30] derived a necessary and sufficient condition for a digraph to admit a $(g, f)$-factor containing $E_1$ and excluding $E_2$, which plays a key role in the proof of Theorem 1.

Lemma 1 (Liu ^[30]). Let $G$ be a digraph, and let $g = (g^{-}, g^{+})$ and $f = (f^{-}, f^{+})$ be pairs of integer-valued functions defined on $V(G)$ satisfying $0\leq g(x)\leq f(x)$ for every $x\in V(G)$. Let $E_1$ and $E_2$ be two disjoint subsets of $E(G)$. Then $G$ admits a $(g, f)$-factor $F$ with $E_1\subseteq E(F)$ and $E_2\cap E(F) = \emptyset$ if and only if $\gamma_{1G}(S, T; g, f)\geq\alpha_S+\beta_T$ and $\gamma_{2G}(S, T; g, f)\geq\alpha_T+\beta_S$ for all vertex subsets $S$ and $T$ of $G$.

In what follows, we always assume that $G$ is a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph, where $m, n, r$ and $k_i$ ($1\leq i\leq m$) are nonnegative integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$. For every $[0, k_i]$-factor $F_i$ and every isolated vertex $x$ of $G$, we admit $d_{F_i}(x) = 0$. We use $I$ to denote the set of all isolated vertices in $G$. If $G-I$ admits a $[0, k_i]$-factor, then $G$ admits also a $[0, k_i]$-factor. Hence, we may assume that $G$ does not admit isolated vertices. For arbitrary $x\in V(G)$, we define

and

Write $p(x) = (p^{-}(x), p^{+}(x))$ and $q(x) = (q^{-}(x), q^{+}(x))$. According to the definitions of $p(x)$ and $q(x)$, we derive

for every $x\in V(G)$.

Lemma 2. Let $G$ be a $[0, k_1+k_2+\cdots+k_m]$-digraph, and let $H_1, H_2, \cdots, H_r$ be independent arcs of $G$, where $m$, $r$ and $k_i$ $(1\leq i\leq m)$ are positive integers with $k_i\geq r+1$. Then $G$ possesses a $[0, k_1]$-factor containing $H_i$ $(1\leq i\leq r)$.

Proof. Let $E_1 = \{H_1, H_2, \cdots, H_r\}$ and $E_2 = \emptyset$. For arbitrary two vertex subsets $S$ and $T$ of $G$, we define $\alpha_S$, $\beta_T$, $\alpha_T$ and $\beta_S$ as before. In light of the definitions of $\alpha_S$, $\beta_T$, $\alpha_T$ and $\beta_S$, we derive

Thus, we admit

and

by $k_1\geq2$, where $\gamma_{1G}(S, T; 0, k_1)$ is defined by Equation (2.1) by replacing $g$ and $f$ by $0$ and $k_1$, and $\gamma_{2G}(S, T; 0, k_1)$ is defined by Equation (2.2) by replacing $g$ and $f$ by $0$ and $k_1$. Then it follows from Lemma 1 that $G$ has a $[0, k_1]$-factor containing $H_i$ $(1\leq i\leq r)$. We finish the proof of Lemma 2.

3.   Proof of Theorem 1

Proof of Theorem 1. We apply induction on $m$ and $n$. According to Lemma 2, Theorem 1 is true for $n = 1$. Hence, we may assume that $n\geq2$. For the inductive step, we assume that Theorem 1 is true for any $[0, k_1+k_2+\cdots+k_{m'}-n'+1]$-digraph $G'$ with $m' < m$, $n' < n$ and $1\leq n'\leq m'$, and any vertex-disjoint $n'$-subdigraphs $H_1', H_2', \cdots, H_r'$ of $G'$. Now, we consider a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph $G$ and any vertex-disjoint $n$-subdigraphs $H_1, H_2, \cdots, H_r$ of $G$.

We take $x_iy_i\in E(H_i)$ for $1\leq i\leq r$. Write $E_1 = \{x_1y_1, x_2y_2, \cdots, x_ry_r\}$ and $E_2 = \Big(\bigcup\limits_{i = 1}^{r}E(H_i)\Big)\setminus E_1$. Thus, we easily see that $|E_1| = r$ and $|E_2| = (n-1)r$. Let $E_{1S}, E_{2S}, E_{1T}, E_{2T}, \alpha_S, \beta_T, \alpha_T, \beta_S, p(x)$ and $q(x)$ be defined as in Section 2. By the definitions of $\alpha_S, \beta_T, \alpha_T$ and $\beta_S$, we derive

Now, we define $\gamma_{1G}(S, T; p, q)$ in Equation (2.1) by replacing $g$ and $f$ by $p$ and $q$, and define $\gamma_{2G}(S, T; p, q)$ in Equation (2.2) by replacing $g$ and $f$ by $p$ and $q$. Then we select two vertex subsets $S$ and $T$ of $G$ satisfying

(a) $\gamma_{1G}(S, T; p, q)-(\alpha_S(S, T; E_1)+\beta_T(S, T; E_2))$ is minimum;

(b) $|S|$ is minimum subject to (a).

Now, we demonstrate the following claim.

Claim 1. If $S\neq\emptyset$, then $q^{+}(x)\leq d_G^{+}(x)-1$ for every $x\in S$, and so $q^{+}(x) = k_m$ for every $x\in S$.

Proof. Set $S_1 = \{x\in S:q^{+}(x)\geq d_G^{+}(x)\}$. In what follows, we verify $S_1 = \emptyset$.

Suppose that $S_1\neq\emptyset$. Let $S_0 = S\setminus S_1$. Thus, we admit

Note that

and

Thus, we derive

which conflicts the choice of $S$. Hence, $S_1 = \emptyset$. And so, if $S\neq\emptyset$, then $q^{+}(x)\leq d_G^{+}(x)-1$ for every $x\in S$. Furthermore, we admit $q^{+}(x) = k_m$ for every $x\in S$. We finish the proof of Claim 1.

The remaining of the proof is dedicated to proving that $G$ possesses a $(p, q)$-factor $F_n$ with $E_1\subseteq E(F_n)$ and $E_2\cap E(F_n) = \emptyset$. According to Lemma 1 and the choice of $S$ and $T$, it suffices to verify that $\gamma_{1G}(S, T; p, q)\geq\alpha_S+\beta_T$ and $\gamma_{2G}(S, T; p, q)\geq\alpha_T+\beta_S$.

Next, we write $\rho = k_1+k_2+\cdots+k_{m-1}-n+2$, $T_1 = \{x:d_G^{-}(x)-\rho > 0, x\in T\}$ and $T_0 = T\setminus T_1$. It is obvious that $p^{-}(x) = 0$ for any $x\in T_0$ and $p^{-}(x) = d_G^{-}(x)-\rho$ for any $x\in T_1$. By the definition of $\beta_T(S, T; E_2)$, we possess

In light of the definitions of $\alpha_S$ and $\beta_T$, we have $\alpha_S\leq\min\{r, |S|\}\leq|S|$ and $\beta_T\leq e_G(V(G)\setminus S, T)$. If $T_1 = \emptyset$, then by Claim 1 we admit

If $S = \emptyset$, then we have $\alpha_S = 0$. It follows from Equation (3.1), $r\geq1$, $2\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$ that

In what follows, we always assume that $S\neq\emptyset$ and $T_1\neq\emptyset$. To demonstrate Theorem 1, we consider two cases.

Case 1. $|S|\geq|T_1|$.

According to Claim 1, the definition of $T_1$, $k_m\geq r+1$ and $|S|\geq|T_1|$, we derive

Case 2. $|S|\leq|T_1|-1$.

By Claim 1, the definitions of $T_0$ and $T_1$, we admit

namely,

Subcase 2.1. $|T_1|\leq k_m-1$.

It follows from Equations (3.1) and (3.2), $r\geq1$, $2\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$ that

Subcase 2.2. $|T_1|\geq k_m$.

Subcase 2.2.1. $|S|\leq(n-1)r-2$.

By $2\leq n\leq m$, $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$ and $\rho = k_1+k_2+\cdots+k_{m-1}-n+2$, we admit

that is,

It follows from Equations (3.2) and (3.3), $|T_1|\geq k_m$, $r\geq1$, $2\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$ that

Subcase 2.2.2. $|S|\geq(n-1)r-1$.

According to $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$, $\rho = k_1+k_2+\cdots+k_{m-1}-n+2$ and $G$ being a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph, we admit $\rho\geq(m-1)(r+1)-n+2$ and $d_G^{+}(S)\leq(k_1+k_2+\cdots+k_m-n+1)|S| = (\rho+k_m-1)|S|$. Combining these with Claim 1, the definition of $T_1$, $|S|\leq|T_1|-1$ and $2\leq n\leq m$, we derive

In conclusion, $\gamma_{1G}(S, T; p, q)\geq\alpha_S(S, T; E_1)+\beta_T(S, T; E_2)$. Similarly, we may demonstrate

It follows from the choice of $S$ and $T$ that $\gamma_{1G}(S', T'; p, q)\geq\alpha_{S'}(S', T'; E_1)+\beta_{T'}(S', T'; E_2)$ and $\gamma_{2G}(S', T'; p, q)\geq\alpha_{T'}(S', T'; E_1)+\beta_{S'}(S', T'; E_2)$ for any two vertex subsets $S'$ and $T'$ of $G$. In light of Lemma 1, $G$ possesses a $(p, q)$-factor $F_n$ with $E_1\subseteq E(F_n)$ and $E_2\cap E(F_n) = \emptyset$. Note that $F_n$ is also a $[0, k_n]$-factor of $G$. It follows from the definitions of $p(x)$ and $q(x)$ that

and

for any $x\in V(G)$. Therefore, $G-F_n$ is a $[0, k_1+k_2+\cdots+k_{m-1}-(n-1)+1]$-digraph. Let $H_i' = H_i-x_iy_i$ for $1\leq i\leq r$. Obviously, $H_1', H_2', \cdots, H_r'$ are $r$ vertex-disjoint $(n-1)$-subdigraphs of $G-F_n$. By the induction hypothesis, there exists a subdigraph $R'$ of $G-F_n$ such that $R'$ admits a $[0, k_i]_{i = 1}^{n-1}$-factorization orthogonal to every $H_i'$, $1\leq i\leq r$. We denote by $R$ the subdigraph of $G$ induced by $E(R')\cup E(F_n)$. Hence, $R$ is a subdigraph of $G$ such that $R$ possesses a $[0, k_i]_{i = 1}^{n}$-factorization orthogonal to every $H_i$, $1\leq i\leq r$. We finish the proof of Theorem 1.

Acknowledgments

We thank the anonymous referees for their careful reading, and for comments on an earlier version that improved the presentation. This work is supported by Six Big Talent Peak of Jiangsu Province (Grant No. JY–022).

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.