On the minimum size of Hamilton saturated hypergraphs

Andrzej Ruciński¹ ; Andrzej Żak²

¹Adam Mickiewicz University
²AGH University of Science and Technology

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

For $1\leq \ell< k$, an $\ell$-overlapping $k$-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 if $H$ does not contain an $\ell$-overlapping hamiltonian $k$-cycle but every hypergraph obtained from $H$ by adding one edge does contain such a cycle. Let sat$(N,k,\ell)$ be the smallest number of edges in an $\ell$-hamiltonian saturated $k$-uniform hypergraph on $N$ vertices. In the case of graphs Clark and Entringer showed in 1983 that sat$(N,2,1)=\lceil \tfrac{3N}2\rceil$. The present authors proved that for $k\geq 3$ and $\ell=1$, as well as for all $0.8k\leq \ell\leq k-1$, sat$(N,k,\ell)=\Theta(N^{\ell})$. Here we prove that sat$(N,2\ell,\ell)=\Theta\left(N^\ell\right)$.

Détail

DOI : 10.37236/8414

Classification : 05C65, 05C35, 05C12
Mots-clés : \(\ell\)-overlapping \(k\)-cycle, \(\ell\)-Hamiltonian saturated hypergraph