错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Dirac-Type Theorem for Uniform Hypergraphs

  • Yue Ma,
  • Xinmin Hou,
  • Jun Gao

摘要

Dirac (Proc Lond Math Soc (3) 2:69–81, 1952) proved that every connected graph of order \(n>2k+1\) n > 2 k + 1 with minimum degree more than k contains a path of length at least \(2k+1\) 2 k + 1 . In this article, we give a hypergraph extension of Dirac’s theorem: Given positive integers nk and r, let H be a connected n-vertex r-graph with no Berge path of length \(2k+1\) 2 k + 1 . (1) If \(k> r\ge 4\) k > r 4 and \(n>2k+1\) n > 2 k + 1 , then \(\delta _1(H)\le \left( {\begin{array}{c}k\\ r-1\end{array}}\right) \) δ 1 ( H ) k r - 1 . Furthermore, there exist hypergraphs \(S'_r(n,k), S_r(n,k)\) S r ( n , k ) , S r ( n , k ) and \(S(sK_{k+1}^{(r)},1)\) S ( s K k + 1 ( r ) , 1 ) such that the equality holds if and only if \(S'_r(n,k)\subseteq H\subseteq S_r(n,k)\) S r ( n , k ) H S r ( n , k ) or \(H\cong S(sK_{k+1}^{(r)},1)\) H S ( s K k + 1 ( r ) , 1 ) ; (2) If \(k\ge r\ge 2\) k r 2 and \(n>2k(r-1)\) n > 2 k ( r - 1 ) , then \(\delta _1(H)\le \left( {\begin{array}{c}k\\ r-1\end{array}}\right) \) δ 1 ( H ) k r - 1 . As an application of (1), we give a better lower bound of the minimum degree than the ones in the Dirac-type results for Berge Hamiltonian cycle given by Bermond et al. (Hypergraphes Hamiltoniens. In: Problémes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloq. Internat. CNRS, vol. 260, pp. 39–43. CNRS, Paris, 1976) or Clemens et al. (Electron Notes Discrete Math 54:181–186, 2016), respectively.