Journal Title
Title of Journal: Graphs and Combinatorics
|
Abbravation: Graphs and Combinatorics
|
|
|
|
|
|
|
|
Authors: Weihua Yang HongJian Lai Hao Li Xiaofeng Guo
Publish Date: 2013/01/23
Volume: 30, Issue: 2, Pages: 501-510
Abstract
Thomassen conjectured that every 4connected line graph is Hamiltonian Chen and Lai Combinatorics and Graph Theory vol 95 World Scientific Singapore pp 53–69 Conjecture 86 of 1995 conjectured that every 3edge connected and essentially 6edge connected graph is collapsible Denote D 3G the set of vertices of degree 3 of graph G For e = uv in EG define de = du + dv − 2 the edge degree of e and xiG = minde e in EG Denote by λ m G the mrestricted edgeconnectivity of G In this paper we prove that a 3edgeconnected graph with xiGgeq7 and lambda3Ggeq7 is collapsible a 3edgeconnected simple graph with xiGgeq7 and lambda3Ggeq6 is collapsible a 3edgeconnected graph with xiGgeq6 lambda2Ggeq4 and lambda3Ggeq6 with at most 24 vertices of degree 3 is collapsible a 3edgeconnected simple graph with xiGgeq6 and lambda3Ggeq5 with at most 24 vertices of degree 3 is collapsible a 3edgeconnected graph with xiGgeq5 and lambda2Ggeq4 with at most 9 vertices of degree 3 is collapsible As a corollary we show that a 4connected line graph LG with minimum degree at least 5 and D 3Gleq9 is Hamiltonian
Keywords:
.
|
Other Papers In This Journal:
|