论文标题
在定定理的指示版本上
On directed version of the Sauer-Spender Theorem
论文作者
论文摘要
令$ d =（v，a）$是订单$ n $的digraph，让$ w $为$ v $的任何子集。我们将$ d $中的$ w $的最低半度定义为$δ^0（w）= \ mbox {min} \ {Δ^+（w），δ^ - （w）\} $，其中$δ^+（w）$是$ d $ d $ d $ d $和$Δ^ - （$ w $ in $ w $ in $ w $ in $ w $ in $ w $ and $ w $ in $ w $ and $ w $和w）$ w $ w $（令$ k $为$ k \ geq 1 $的整数。 In this paper, we prove that for any positive integer partition $|W|=\sum_{i=1}^{k}n_i$ with $n_i\geq 2$ for each $i$, if $δ^0(W)\geq \frac{3n-3}{4}$, then there are $k$ vertex disjoint cycles $ c_1，\ ldots，c_k $ in $ d $中的$ c_i $ c_i $完全包含$ w $的$ n_i $ vertices。此外，如果$ k = 1 $，则可以将$δ^0（w）$的下限提高到$ \ frac {n} {2} $，而$ \ frac {n} {2} {2}+| w | -1 $如果$ n \ n \ geq 2 | w | $。 最小半学位条件$δ^0（w）\ geq \ frac {3n-3} {4} $在某种意义上是尖锐的，此结果部分证实了Wang [Graph and Combinatorics 16（2000）453-462]的猜想。它也是在图中的顶点分离周期上的Sauer-Gentender定理的定向版本[J.组合。理论B，25（1978）295-302]。
Let $D=(V,A)$ be a digraph of order $n$ and let $W$ be any subset of $V$. We define the minimum semi-degree of $W$ in $D$ to be $δ^0(W)=\mbox{min}\{δ^+(W),δ^-(W)\}$, where $δ^+(W)$ is the minimum out-degree of $W$ in $D$ and $δ^-(W)$ is the minimum in-degree of $W$ in $D$. Let $k$ be an integer with $k\geq 1$. In this paper, we prove that for any positive integer partition $|W|=\sum_{i=1}^{k}n_i$ with $n_i\geq 2$ for each $i$, if $δ^0(W)\geq \frac{3n-3}{4}$, then there are $k$ vertex disjoint cycles $C_1,\ldots,C_k$ in $D$ such that each $C_i$ contains exactly $n_i$ vertices of $W$. Moreover, the lower bound of $δ^0(W)$ can be improved to $\frac{n}{2}$ if $k=1$, and $\frac{n}{2}+|W|-1$ if $n\geq 2|W|$. The minimum semi-degree condition $δ^0(W)\geq \frac{3n-3}{4}$ is sharp in some sense and this result partially confirms the conjecture posed by Wang [Graphs and Combinatorics 16 (2000) 453-462]. It is also a directed version of the Sauer-Spender Theorem on vertex disjoint cycles in graphs [J. Combin. Theory B, 25 (1978) 295-302].
