On Hamilton-chain saturated uniform hypergraphs
Andrzej Zak, Aneta Dudek
Abstract
We say that a hypergraph H is hamiltonian chain saturated
if H does not contain a hamiltonian chain but by adding
any new edge we create a hamiltonian chain in H. In this
paper we ask about the smallest size of a k-uniform
hamiltonian chain saturated hypergraph. We present a construction of a
family of k-uniform hamiltonian chain saturated
hypergraphs with O(nk-1/2) edges.
Full Text: PDF PostScript