Article ID Journal Published Year Pages File Type
4653791 European Journal of Combinatorics 2013 12 Pages PDF
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, for each k≥3, we establish the right order of magnitude nk−1 for the size of the smallest k-uniform hamiltonian chain saturated hypergraph. This solves an open problem of G.Y. Katona.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,