On hamiltonian chain saturated uniform hypergraphs

被引：0

作者：

Dudek, Aneta ^{[1
]}

Zak, Andrzej ^{[1
]}

机构：

[1] AGH Univ Sci & Technol, Krakow, Poland

来源：

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | 2012年 / 14卷 / 01期

关键词：

saturated hypergraph; hamiltonian path; hamiltonian cycle; hamiltonian chain; GRAPHS; SIZE;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：21 / 28

页数：8

共 25 条

[1]

[Anonymous], CYCLE SATURATE UNPUB

[2] C3 saturated graphs [J].

Ashkenazi, Y .

DISCRETE MATHEMATICS, 2005, 297 (1-3) :152-158

[3] Cycle-saturated graphs of minimum size [J].

Barefoot, CA ;

Clark, LH ;

Entringer, RC ;

Porter, TD ;

Szekely, LA ;

Tuza, Z .

DISCRETE MATHEMATICS, 1996, 150 (1-3) :31-48

[4]

Bohman T, 2010, J COMB, V1, P149

[5] ON GENERALIZED GRAPHS [J].

BOLLOBAS, B .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1965, 16 (3-4) :447-&

[6] VARIATIONS ON HAMILTONIAN THEME [J].

BONDY, JA .

CANADIAN MATHEMATICAL BULLETIN, 1972, 15 (01) :57-&

[7]

Chen GT, 2008, ELECTRON J COMB, V15

[8] Minimum C5-Saturated Graphs [J].

Chen, Ya-Chen .

JOURNAL OF GRAPH THEORY, 2009, 61 (02) :111-126

[9]

Chen Ya-Chen, MINIMUM K2 3 S UNPUB

[10]

Clark L.H., 1983, PERIOD MATH HUNGAR, V14, P57

← 1 2 3 →