A Dirac-Type Theorem for Uniform Hypergraphs

• Published in: Graphs and combinatorics 2024-08, Vol.40 (4), Article 76
• Main Authors: Ma, Yue, Hou, Xinmin, Gao, Jun
• Format: Article
• Language: English
• Subjects: Combinatorics; Engineering Design; Graph theory; Graphs; Lower bounds; Mathematics; Mathematics and Statistics; Original Paper; Theorems
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-024-02802-8

Dirac (Proc Lond Math Soc (3) 2:69–81, 1952) proved that every connected graph of order n > 2 k + 1 with minimum degree more than k contains a path of length at least 2 k + 1 . In this article, we give a hypergraph extension of Dirac’s theorem: Given positive integers n ,  k and r , let H be a connected n -vertex r -graph with no Berge path of length 2 k + 1 . (1) If k > r ≥ 4 and n > 2 k + 1 , then δ 1 ( H ) ≤ k r - 1 . Furthermore, there exist hypergraphs S r ′ ( n , k ) , S r ( n , k ) and S ( s K k + 1 ( r ) , 1 ) such that the equality holds if and only if S r ′ ( n , k ) ⊆ H ⊆ S r ( n , k ) or H ≅ S ( s K k + 1 ( r ) , 1 ) ; (2) If k ≥ r ≥ 2 and n > 2 k ( r - 1 ) , then δ 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.