Collapsible graphs and Hamiltonian connectedness of line graphs

详细信息    查看全文

• 作者：Weihua Yang^a ; ^{ywh222@163.com} ; Hongjian Lai^b ; ^c ; Hao Li^a ; Xiaofeng Guo^d
• 关键词：Thomassen&rsquo ; s conjecture ; Line graph ; Super-Eulerian graph ; Collapsible graph ; Hamiltonian line graph ; Dominating Eulerian subgraph ; Edge connectivity
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：August, 2012
• 年：2012
• 卷：160
• 期：12
• 页码：1837-1844
• 全文大小：222 K

文摘

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics¡ªan update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, World Scientific, Singapore/London, 1995, pp. 53-69, Conjecture 8.6] conjectured that every 3-edge connected, essentially 6-edge connected graph is collapsible. In this paper, we prove the following results. (1) Every 3-edge connected, essentially 6-edge connected graph with edge-degree at least 7 is collapsible. (2) Every 3-edge connected, essentially 5-edge connected graph with edge-degree at least 6 and at most 24 vertices of degree 3 is collapsible which implies that 5-connected line graph with minimum degree at least 6 of a graph with at most 24 vertices of degree 3 is Hamiltonian. (3) Every 3-connected, essentially 11-connected line graph is Hamilton-connected which strengthens the result in [H.-J. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory, Ser. B 96 (2006) 571-576] by Lai et al. (4) Every 7-connected line graph is Hamiltonian connected which is proved by a method different from Zhan¡¯s. By using the multigraph closure introduced by Ryj¨¢?ek and Vr¨¢na which turns a claw-free graph into the line graph of a multigraph while preserving its Hamilton-connectedness, the results (3) and (4) can be extended to claw-free graphs.