Dudek, Aneta and Zak, Andrzej - On hamiltonian chain saturated uniform hypergraphs

dmtcs:571 - Discrete Mathematics & Theoretical Computer Science, January 26, 2012, Vol. 14 no. 1
On hamiltonian chain saturated uniform hypergraphs

Authors: Dudek, Aneta and Zak, Andrzej

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(n(k-1/2)) edges.


Source : oai:HAL:hal-00990568v1
Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: January 26, 2012
Submitted on: April 15, 2010
Keywords: saturated hypergraph,hamiltonian path,hamiltonian cycle,hamiltonian chain,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 42 times.
This article's PDF has been downloaded 78 times.