Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648560 | Discrete Mathematics | 2010 | 5 Pages |
Abstract
We say that a hypergraph HH is hamiltonian path (cycle) saturated if HH does not contain an open (closed) hamiltonian chain but by adding any new edge we create an open (closed) hamiltonian chain in HH. In this paper we ask about the smallest size of an rr-uniform hamiltonian path (cycle) saturated hypergraph, mainly for r=3r=3. We present a construction of a family of 3-uniform path (cycle) saturated hamiltonian hypergraphs with O(n5/2)O(n5/2) edges. On the other hand we prove that the number of edges in an rr-uniform hamiltonian path (cycle) saturated hypergraph is at least Ω(nr−1)Ω(nr−1).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Aneta Dudek, Andrzej Żak, Gyula Y. Katona,