We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Collapsible Graphs and Hamiltonicity of Line Graphs.
- Authors
Yang, Weihua; Lai, Hong-Jian; Li, Hao; Guo, Xiaofeng
- Abstract
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53-69; Conjecture 8.6 of ) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D( G) the set of vertices of degree 3 of graph G. For $${e = uv \in E(G)}$$, define d( e) = d( u) + d( v) − 2 the edge degree of e, and $${\xi(G) = \min\{d(e) : e \in E(G)\}}$$. Denote by λ( G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with $${\xi(G)\geq7}$$, and $${\lambda^3(G)\geq7}$$ is collapsible; a 3-edge-connected simple graph with $${\xi(G)\geq7}$$, and $${\lambda^3(G)\geq6}$$ is collapsible; a 3-edge-connected graph with $${\xi(G)\geq6}$$, $${\lambda^2(G)\geq4}$$, and $${\lambda^3(G)\geq6}$$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with $${\xi(G)\geq6}$$, and $${\lambda^3(G)\geq5}$$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with $${\xi(G)\geq5}$$, and $${\lambda^2(G)\geq4}$$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L( G) with minimum degree at least 5 and $${|D_3(G)|\leq9}$$ is Hamiltonian.
- Subjects
GRAPH theory; GRAPH connectivity; MATHEMATICAL analysis; SET theory; HAMILTONIAN systems
- Publication
Graphs & Combinatorics, 2014, Vol 30, Issue 2, p501
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-012-1280-x