Minimum degree ensuring that a hypergraph is hamiltonian-connected

Abstract

A hypergraph $H$ is hamiltonian-connected if for any distinct vertices $x$ and $y$, $H$ contains a hamiltonian Berge path from $x$ to $y$. We find for all $3\le r<n$, exact lower bounds on minimum degree $\delta (n,r)$ of an $n$-vertex $r$-uniform hypergraph $H$ guaranteeing that $H$ is hamiltonian-connected. It turns out that for $3\le n/2<r<n$, $\delta (n,r)$ is 1 less than the degree bound guaranteeing the existence of a hamiltonian Berge cycle. Moreover, unlike for graphs, for each $r\ge 3$ there exists an $r$-uniform hypergraph that is hamiltonian-connected but does not contain a hamiltonian Berge cycle.

22 pages, 1 figure. Final version to appear in the European Journal of Combinatorics