3-Connected {K 1,3, P 9}-Free Graphs are Hamiltonian-Connected

被引：12

作者：

Bian, Qiuju ^{[1
]}

Gould, Ronald J. ^{[2
]}

Horn, Paul ^{[3
]}

Janiszewski, Susan ^{[2
]}

La Fleur, Steven ^{[2
]}

Wrayno, Paul ^{[4
]}

机构：

[1] Shandong Univ Technol, Sch Math & Informat Sci, Zibo 50100, Peoples R China

[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

[3] Harvard Univ, Dept Math, FAS, Cambridge, MA 02138 USA

[4] Western Kentucky Univ, Dept Math, Bowling Green, KY 42101 USA

来源：

GRAPHS AND COMBINATORICS | 2014年 / 30卷 / 05期

关键词：

Hamilton-connected; 3-Connected; Claw-free; Dominating; Closure; CLAW-FREE GRAPHS;

D O I：

10.1007/s00373-013-1344-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We investigate pairs of forbidden subgraphs that imply a 3-connected graph is Hamiltonian-connected. In particular we show that the pair {K (1,3), P (9)} is such a pair. As it is known that P (10) cannot replace P (9), this result is best possible. Further, we show that certain other graphs are not possible.

引用

页码：1099 / 1122

页数：24

共 9 条

[1]

[Anonymous], 2000, B I COMBIN APPL

[2]

Bedrossian P., 1991, Thesis

[3] 9-connected claw-free graphs are Hamilton-connected [J].

Brandt, S .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 75 (02) :167-173

[4] Forbidden subgraphs that imply hamiltonian-connectedness [J].

Broersma, H ;

Faudree, RJ ;

Huck, A ;

Trommel, H ;

Veldman, HJ .

JOURNAL OF GRAPH THEORY, 2002, 40 (02) :104-119

[5]

Chartrand G., 1996, Graphs & Digraphs, V3rd

[6]

Faudree J. R., 2010, FORBIDDEN PAIRS IMPL

[7] Characterizing forbidden pairs for Hamiltonian properties [J].

Faudree, RJ ;

Gould, RJ .

DISCRETE MATHEMATICS, 1997, 173 (1-3) :45-60

[8] On graph closures [J].

Kelmans, A .

DISCRETE MATHEMATICS, 2003, 271 (1-3) :141-168

[9] HAMILTONICITY IN CLAW-FREE GRAPHS [J].

SHEPHERD, FB .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 53 (02) :173-194

← 1 →