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 hypergraphs

Authors: Aneta Dudek ; Andrzej Zak

    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]

    Share

    Consultation statistics

    This page has been seen 179 times.
    This article's PDF has been downloaded 518 times.