
Andrzej Ruciński

Andrzej Żak
Keywords:
Saturation number, Hamiltonian cycles, Hypergraphs
Abstract
For $1\leq \ell< k$, an $\ell$overlapping cycle is a $k$uniform hypergraph in which, for some cyclic vertex ordering, every edge consists of $k$ consecutive vertices and every two consecutive edges share exactly $\ell$ vertices. A $k$uniform hypergraph $H$ is $\ell$Hamiltonian saturated, $1\le \ell\le k1$, if $H$ does not contain an $\ell$overlapping Hamiltonian cycle $C^{(k)}_n(\ell)$ but every hypergraph obtained from $H$ by adding one more edge does contain $C^{(k)}_n(\ell)$. Let $sat(n,k,\ell)$ be the smallest number of edges in an $\ell$Hamiltonian saturated $k$uniform hypergraph on $n$ vertices. Clark and Entringer proved in 1983 that $sat(n,2,1)=\lceil \tfrac{3n}2\rceil$ and the second author showed recently that $sat(n,k,k1)=\Theta(n^{k1})$ for every $k\ge2$. In this paper we prove that $sat(n,k,\ell)=\Theta(n^{\ell})$ for $\ell=1$ as well as for all $k\ge5$ and $\ell\ge0.8k$.