10-tough chordal graphs are Hamiltonian

被引：13

作者：

Kabela, Adam ^{[1
,2
]}

Kaiser, Tomas ^{[2
,3
]}

机构：

[1] Univ West Bohemia, Dept Math, Plzen, Czech Republic

[2] Univ West Bohemia, European Ctr Excellence NTIS New Technol Informat, Plzen, Czech Republic

[3] Univ West Bohemia, Dept Math, Inst Theoret Comp Sci CE ITI, Plzen, Czech Republic

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2017年 / 122卷

关键词：

Toughness; Hamilton cycle; Chordal graph; Hamilton-connected graph; TOUGHNESS;

D O I：

10.1016/j.jctb.2016.07.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Chen et al. (1998) proved that every 18-tough chordal graph has a Hamilton cycle. Improving upon their bound, we show that every 10-tough chordal graph is Hamiltonian (in fact, Hamilton-connected). We use Aharoni and Haxell's hypergraph extension of Hall's Theorem as our main tool. (C) 2016 Elsevier Inc. All rights reserved.

引用

页码：417 / 427

页数：11

共 11 条

[1]

Aharoni R, 2000, J GRAPH THEOR, V35, P83, DOI 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO

[2]

2-V

[3] Toughness in graphs - A survey [J].

Bauer, D ;

Broersma, H ;

Schmeichel, E .

GRAPHS AND COMBINATORICS, 2006, 22 (01) :1-35

[4] Not every 2-tough graph is Hamiltonian [J].

Bauer, D ;

Broersma, HJ ;

Veldman, HJ .

DISCRETE APPLIED MATHEMATICS, 2000, 99 (1-3) :317-321

[5]

Böhme T, 1999, J GRAPH THEOR, V32, P405

[6]

Chen GT, 1998, NETWORKS, V31, P29, DOI 10.1002/(SICI)1097-0037(199801)31:1<29::AID-NET4>3.0.CO

[7]

2-M

[8]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[9]

Gavril F., 1974, Journal of Combinatorial Theory, Series B, V16, P47, DOI 10.1016/0095-8956(74)90094-X

[10] FINDING HAMILTONIAN CIRCUITS IN INTERVAL-GRAPHS [J].

KEIL, JM .

INFORMATION PROCESSING LETTERS, 1985, 20 (04) :201-206

← 1 2 →