×

Upper bounds on the minimum size of Hamilton saturated hypergraphs. (English) Zbl 1351.05165

Summary: For \(1\leqslant \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 \(\mathrm{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 L. Clark and R. Entringer [Period. Math. Hung. 14, 57–68 (1983; Zbl 0489.05038)] showed that \(\mathrm{sat}(n,2,1)=\lceil\frac{3n}{2}\rceil\). The present authors proved that for \(k\geqslant 3\) and \(\ell=1\), as well as for all \(0.8k\leqslant \ell\leq k-1\), \(\mathrm{sat}(n,k,\ell)=\Theta(n^{\ell})\). In this paper we prove two upper bounds which cover the remaining range of \(\ell\). The first, quite technical one, restricted to \(\ell\geqslant\frac{k+1}{2}\), implies in particular that for \(\ell=\frac{2}{3}k\) and \(\ell=\frac{3}{4}k\) we have \(\mathrm{sat}(n,k,\ell)=O(n^{\ell+1})\). Our main result provides an upper bound \(\mathrm{sat}(n,k,\ell)=O(n^{\frac{k+\ell}2})\) valid for all \(k\) and \(\ell\). In the smallest open case we improve it further to \(\mathrm{sat}(n,4,2)=O(n^{14/5})\).

MSC:

05C65 Hypergraphs
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 0489.05038

References:

[1] L. Clark and R. Entringer, Smallest maximally non-Hamiltonian graphs, Period. Math. Hungar. 14(1), 1983, 57-68. · Zbl 0489.05038
[2] R. Glebov, Y. Person and W. Weps, On extremal hypergraphs for Hamiltonian cycles. European J. Combin., 33:544-555, 2012. · Zbl 1237.05142
[3] G. Y. Katona, Hamiltonian chains in hypergraphs, A survey. Graphs, Combinatorics, Algorithms and its Applications, (ed. S. Arumugam, B. D. Acharya, S. B. Rao), Narosa Publishing House 2004. the electronic journal of combinatorics 23(4) (2016), #P4.12 25
[4] G. Y. Katona and H. Kierstead,Hamiltonian chains in hypergraphs. J. Graph Theory, 30:205-212, 1999. · Zbl 0924.05050
[5] A. Ruci´nski and A. ˙Zak, Hamilton saturated hypergraphs of essentially minimum size, Electr. J. Combin., 20(2), 2013, #P25. · Zbl 1266.05108
[6] A. ˙Zak, Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs. European J. Combin., 34:724-735, 2013. · Zbl 1259.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.