On the minimum size of Hamilton saturated hypergraphs

DOI10.37236/8414MaRDI QIDQ2213813zbMATH OpenOpenAlexFDO

Authors Andrzej Żak, Andrzej Ruciński

Publication date 3 December 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/8414

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(\ell\)-Hamiltonian saturated hypergraph\(\ell\)-overlapping \(k\)-cycle

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Review text

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 \textit{L. Clark} and \textit{R. Entringer} showed [Period. Math. Hung. 14, 57--68 (1983; Zbl 0489.05038)] 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\leqslant k-1\), \(\mathrm{sat}(N,k,\ell)=\Theta(N^{\ell})\). Here we prove that \(\mathrm{sat}(N,2\ell,\ell)=\Theta\left(N^\ell\right)\).

Recommendations

• Hamilton saturated hypergraphs of essentially minimum size
• Upper bounds on the minimum size of Hamilton saturated hypergraphs
• Constructing sparsest -Hamiltonian saturated k-uniform hypergraphs for a wide range of
• Hamilton-chain saturated hypergraphs
• scientific article; zbMATH DE number 6273737

Cites work

• Hamilton saturated hypergraphs of essentially minimum size
• Hamiltonian chains in hypergraphs
• scientific article; zbMATH DE number 4043879 (Why is no real title available?)
• On extremal hypergraphs for Hamiltonian cycles
• Smallest maximally nonhamiltonian graphs
• Smallest maximally nonhamiltonian graphs. II
• Upper bounds on the minimum size of Hamilton saturated hypergraphs
• Variations on the Hamiltonian Theme

Cited in

(7)

• Growth order for the size of smallest Hamiltonian chain saturated uniform hypergraphs
• Hamilton saturated hypergraphs of essentially minimum size
• Constructing sparsest -Hamiltonian saturated k-uniform hypergraphs for a wide range of
• Hamiltonian path saturated graphs with small size
• scientific article; zbMATH DE number 6273737 (Why is no real title available?)
• Upper bounds on the minimum size of Hamilton saturated hypergraphs
• Hamilton-chain saturated hypergraphs

This page was built for publication: On the minimum size of Hamilton saturated hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2213813)