首页 | 本学科首页   官方微博 | 高级检索  
     


On s-hamiltonian line graphs of claw-free graphs
Authors:Hong-Jian Lai  Mingquan Zhan  Taoye Zhang  Ju Zhou
Abstract:For an integer s0, a graph G is s-hamiltonian if for any vertex subset S?V(G) with |S|s, G?S is hamiltonian, and G is s-hamiltonian connected if for any vertex subset S?V(G) with |S|s, G?S is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of s-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for s2, a line graph L(G) is s-hamiltonian if and only if L(G) is (s+2)-connected. In this paper we prove the following.(i) For an integer s2, the line graph L(G) of a claw-free graph G is s-hamiltonian if and only if L(G) is (s+2)-connected.(ii) The line graph L(G) of a claw-free graph G is 1-hamiltonian connected if and only if L(G) is 4-connected.
Keywords:Claw-free graphs  Line graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号