A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs

Abstract

Let $D$ be a digraph. We define the minimum semi-degree of $D$ as ${\delta }^0(D):=\min \{{\delta }^{+}(D),{\delta }^{-}(D)\}$. Let $k$ be a positive integer, and let $S=\{s\}$ and $T=\{t_1,\dots ,t_k\}$ be any two disjoint subsets of $V(D)$. A set of $k$ internally disjoint paths joining source set $S$ and sink set $T$ that cover all vertices $D$ are called a one-to-many $k$-disjoint directed path cover ($k$-DDPC for short) of $D$. A digraph $D$ is semicomplete if for every pair $x,y$ of vertices of it, there is at least one arc between $x$ and $y$. In this paper, we prove that every semicomplete digraph $D$ of sufficiently large order $n$ with ${\delta }^0(D)\ge \lceil (n+k-1)/2\rceil$ has a one-to-many $k$-DDPC joining any disjoint source set $S$ and sink set $T$, where $S=\{s\},T=\{t_1,\dots ,t_k\}$.