A minimum semi-degree condition for unpaired many-to-many disjoint path covers in digraphs

Abstract

For a digraph $D$, let ${\delta }^0(D)=\min \{{\delta }^{+}(D),{\delta }^{-}(D)\}$ be the minimum semi-degree of $D$. A set of $k$ vertex-disjoint paths, $\{P_1,\dots ,P_k\}$, joining a disjoint source set $S=\{s_1,\dots ,s_k\}$ and sink set $T=\{t_1,\dots ,t_k\}$ is called an unpaired many-to-many $k$-disjoint directed path cover ($k$-DDPC for short) of $D$, if each $P_j$ joins $s_j$ and $t_{\sigma (j)}$ for some permutation $\sigma$ on $\{1,\dots ,k\}$ and ${\bigcup }_{j=1}^{k}V(P_j)=V(D)$. In this paper, we give a new proof for the following result that every digraph $D$ with ${\delta }^0(D)\ge \lceil (n+k)/2\rceil$ has an unpaired many-to-many $k$-DDPC joining any disjoint source set $S$ and sink set $T$, where $S=\{s_1,\dots ,s_k\}$ and $T=\{t_1,\dots ,t_k\}$. Moreover, we show that the bound on the minimum semi-degree is best possible when $n\ge 3k$.

We find a mistake on the proof of the claim at page 5