论文标题
一对一对一多一不相交路径的最低半度条件覆盖在半完整的挖掘中
A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs
论文作者
论文摘要
令$ d $为挖掘物。我们将$ d $的最小半学位定义为$δ^{0}（d）：= \ min \ {δ^{+{+} {+}（d），Δ^^{ - }（d）\} $。令$ k $为正整数，让$ s = \ {s \} $和$ t = \ {t_ {1}，\ dots，t_ {k} \} $是$ v（d）$的任何两个不相交的子集。一组$ k $的内部不相交路径连接源集合$ s $ s $ s $ s $ s $ t $，覆盖所有顶点$ d $称为一对一的$ k $ -disjoint指示路径盖（$ k $ -ddpc for Short for Short）为$ d $。如果每对$ x，y $的顶点，则digraph $ d $是半完整的，至少有$ x $和$ y $的弧线。 在本文中，我们证明，每个半完整的digraph $ d $ d $ a $ d $ $ n $，$δ^{0}（d）（d）\ geq \ lceil（n+k-1）/2 \ rceil $都有一对多$ k $ -dddpc加入任何不相关的s $ s $ s $ s $ s $ s $ t $ t $， \ {t_ {1}，\ dots，t_ {k} \} $。
Let $D$ be a digraph. We define the minimum semi-degree of $D$ as $δ^{0}(D) := \min \{δ^{+}(D), δ^{-}(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 $δ^{0}(D) \geq \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}\}$.
