|
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
if \(H\) does not contain an \(\ell\)-overlapping Hamiltonian cycle
but every hypergraph obtained from \(H\) by adding one more 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 [1] proved in 1983 that
sat\((n,2,1)=\lceil \tfrac{3n}2\rceil\).
For hypergraphs with \(k\ge3\) it seems to be quite hard to obtain such precise results. Therefore,
the emphasis is put on the order of magnitude of sat\((n,k,\ell)\).
We proved that for \(k\geq 3\) and \(\ell=1\) as well as for all \(0.8k\leq \ell\leq k-1\)
\begin{align}
{\rm sat}(n,k,\ell)=\Theta(n^{\ell}),
\end{align}
see [2,3]. Recently, we have got also some partial results:
sat\((n,k,\ell)=O(n^{(k+\ell)/2})\) and, in the smallest open case, sat\((n,4,2)=O(n^{14/5})\).
|
References- L. Clark and R. Entringer, Smallest maximally non-Hamiltonian
graphs, Period. Math. Hungar. 14(1), 1983, 57-68.
-
A. Ruciński and A. .Zak, Hamilton saturated hypergraphs of essentially minimum size,
Electr. J. Combin. , 20(2), 2013, P25.
- A. .Zak, Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs,
Eur. J. Combin. 34(4), 2013, 724-735.
|
