Toughness and Hamiltonicity of a class of planar graphs

被引：4

作者：

Gerlach, T ^{[1
]}

机构：

[1] Tech Univ Ilmenau, Dept Math, D-98684 Ilmenau, Germany

来源：

DISCRETE MATHEMATICS | 2004年 / 286卷 / 1-2期

关键词：

Hamiltonian cycles; planar graph; chordal graph; toughness;

D O I：

10.1016/j.disc.2003.11.046

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is called chordal if every cycle of G of length at least four has a chord. By a theorem of Bohme, Harant and Tkac more than 1-tough chordal planar graphs are Hamiltonian. We prove that this is even true for more than 1-tough planar graphs under the weaker assumption that separating cycles of length at least four have chords. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：61 / 65

页数：5

共 14 条

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

Bauer, D ;

Broersma, HJ ;

Veldman, HJ .

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

[2]

BERMOND JC, 1978, SELECTED TOPICS GRAP, P127

[3]

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

[4]

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

[5]

DIESTEL R, 1997, GRAPH THEORY GRADUAT, V173, P61801

[6] AN UPPER BOUND ON THE SHORTNESS EXPONENT OF 1-TOUGH, MAXIMAL PLANAR GRAPHS [J].

DILLENCOURT, MB .

DISCRETE MATHEMATICS, 1991, 90 (01) :93-97

[7]

Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]

[8] TOUGHNESS AND THE EXISTENCE OF K-FACTORS [J].

ENOMOTO, H ;

JACKSON, B ;

KATERINIS, P ;

SAITO, A .

JOURNAL OF GRAPH THEORY, 1985, 9 (01) :87-95

[9]

Grunbaum B., 1973, Journal of Combinatorial Theory, Series A, V14, P364, DOI 10.1016/0097-3165(73)90012-5

[10] TOUGHNESS AND NONHAMILTONICITY OF POLYHEDRAL GRAPHS [J].

HARANT, J .

DISCRETE MATHEMATICS, 1993, 113 (1-3) :249-253

← 1 2 →