Hamilton-chain saturated hypergraphs

Dudek, A; Zak, A; Katona, G Y [Katona, Gyula Y. (gráfelmélet), szerző] Számítástudományi és Információelméleti Tanszék (BME / VIK)

Angol nyelvű Tudományos Szakcikk (Folyóiratcikk)
Megjelent: DISCRETE MATHEMATICS 0012-365X 1872-681X 310 (6-7) pp. 1172-1176 2010
  • SJR Scopus - Discrete Mathematics and Combinatorics: Q2
Azonosítók
Szakterületek:
    We say that a hypergraph H is hamiltonian path (cycle) saturated if H does not contain an open (closed) hamiltonian chain but by adding any new edge we create an open (closed) hamiltonian chain in H. In this paper we ask about the smallest size of an r-uniform hamiltonian path (cycle) saturated hypergraph, mainly for r = 3. We present a construction of a family of 3-uniform path (cycle) saturated hamiltonian hypergraphs with O (n5 / 2) edges. On the other hand we prove that the number of edges in an r-uniform hamiltonian path (cycle) saturated hypergraph is at least Ω (nr - 1). © 2009 Elsevier B.V. All rights reserved.
    Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
    2021-08-04 23:50