Aneta Dudek ; Andrzej Zak - On hamiltonian chain saturated uniform hypergraphs

dmtcs:571 - Discrete Mathematics & Theoretical Computer Science, January 26, 2012, Vol. 14 no. 1 - https://doi.org/10.46298/dmtcs.571
On hamiltonian chain saturated uniform hypergraphsArticle

Authors: Aneta Dudek 1; Andrzej Zak 1

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.


Volume: Vol. 14 no. 1
Section: Graph and Algorithms
Published on: January 26, 2012
Accepted on: June 9, 2015
Submitted on: April 15, 2010
Keywords: saturated hypergraph,hamiltonian path,hamiltonian cycle,hamiltonian chain,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 360 times.
This article's PDF has been downloaded 679 times.