Hamilton saturated hypergraphs of essentially minimum size

Andrzej Ruciński¹ ; Andrzej Żak²

¹Adam Mickiewicz University
²AGH University of Science and Technology

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

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 k-1$, 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,k-1)=\Theta(n^{k-1})$ 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$.

Détail

DOI : 10.37236/2484

Classification : 05C65, 05C45, 05C38, 05C35
Mots-clés : saturation number, Hamiltonian cycles, hypergraphs