Discrete Mathematics & Theoretical Computer Science, Vol 14, No 1 (2012)

Font Size:  Small  Medium  Large

On Hamilton-chain saturated uniform hypergraphs

Andrzej Zak, Aneta Dudek


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