Dirac's Theorem for hamiltonian Berge cycles in uniform hypergraphs

Abstract

The famous Dirac's Theorem gives an exact bound on the minimum degree of an $n$-vertex graph guaranteeing the existence of a hamiltonian cycle. We prove exact bounds of similar type for hamiltonian Berge cycles in $r$-uniform, $n$-vertex hypergraphs for all $3\le r<n$. The bounds are different for $r<n/2$ and $r\ge n/2$. We also give bounds on the minimum degree guaranteeing existence of Berge cycles of length at least $k$ in such hypergraphs; the bounds are exact for all $k\ge n/2$.

23 pages. Updated statement of Claim 3.1

References in corpus (1)

• A Rainbow Dirac's Theorem