摘要 Abstract
我们研究了在满足半度条件下的定向图中具有两个块的定向路径的存在性。对于正整数 $k$ 和 $\ell$,其中 $k/2 \leq \ell < k$,我们建立了保证包含大小为 $\ell$ 和 $k-\ell$ 的两个块的所有定向路径的半度函数。作为推论,我们证明了每个所有入度和出度至少为 $3k/4$ 的定向图都包含具有 $k$ 条弧的两个块的路径。我们的结果推广了关于Stein猜想及相关问题的先前工作。
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes $\ell$ and $k-\ell$. As a corollary, we show that every oriented graph with all in- and out-degrees at least $3k/4$ contains every two-block path with $k$ arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths.