Every 3-connected, essentially 11-connected line graph is Hamiltonian

被引：17

作者：

Lai, HH ^{[1
]}

Shao, YH

Wu, HH

Zhou, J

机构：

[1] W Virginia Univ, Dept Math, Morgantown, WV 26506 USA

[2] Ohio Univ So, Ironton, OH 45638 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2006年 / 96卷 / 04期

关键词：

line graph; claw-free graph; super-Eulerian graphs; collapsible graph; Hamiltonian graph; dominating Eulerian subgraph; essential connectivity;

D O I：

10.1016/j.jctb.2005.11.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Thomassen conjectured that every 4-connected line graph is Hamiltonian. A vertex cut X of G is essential if G-X has at least two non-trivial components. We prove that every 3-connected. essentially 11-connected line graph is Hamiltonian. Using Ryjcaek's line graph closure. it follows that every 3-connected. essentially 11-connected claw-free graph is Hamiltonian. (C) 2005 Elsevier Inc. All rights reserved.

引用

页码：571 / 576

页数：6

共 7 条

[1]

Bondy J.A., 2008, GRAD TEXTS MATH

[2] A REDUCTION METHOD TO FIND SPANNING EULERIAN SUBGRAPHS [J].