A Dirac-Type Theorem for Uniform Hypergraphs
A Dirac-Type Theorem for Uniform Hypergraphs
复制标题
一致超图的狄拉克型定理
作者：
Yue Ma;Xinmin Hou;Jun
Dirac（1952）证明了：每一个阶数n>2k+1且最小度大于k的连通图都含有一条长度至少为2k +1的路。在本文中，我们表明，
(a)对k>r\ge 3，n>2k（r-1）阶连通r-一致超图（H>{k\choose r-1}）包含长度至少为2k +1的Berge路;
(b)对k>r\ge 4，若H是两类极超图之一，则对任意n>2k+1阶连通r-一致超图H，若H满足\delta_1（H）\ge {k\choose r-1}$，则H包含一条长度至少为2k +1$的Berge路.
作为（B）的一个应用，我们给出了一个比Bermond，Germa，Heydemann，and Sotteau（1976）证明的Berge Hamilton圈的Dirac型定理更好的最小次数下界.
Dirac (1952) proved that every connected graph of order $n>2k+1$ with minimum degree more than $k$ contains a path of length at least $2k+1$. In this paper, we show that
(a) for $k>r\ge 3$, every connected $r$-uniform hypergragh of order $n>2k(r-1)$ with $\delta_1(H)>{k\choose r-1}$ contains a Berge path of length at least $2k+1$;
(b) for $k>r\ge 4$, every connected $r$-uniform hypergragh $H$ of order $n>2k+1$ with $\delta_1(H)\ge {k\choose r-1}$ contains a Berge path of length at least $2k+1$, unless $H$ is one of the two kinds of described extremal hypergraphs.
As an application of (b), we give a much better lower bound of the minimum degree than the one given in a Dirac-type theorem for Berge Hamiltonian cycle proved by Bermond, Germa, Heydemann, and Sotteau (1976).