On 3-connected hamiltonian line graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Ye Chen^a ; ^{chenye@math.wvu.edu} ; Suohai Fan^b ; ^{tfsh@jnu.edu.cn} ; Hong-Jian Lai^c ; ^a ; ^{hjlai@math.wvu.edu}
• 关键词：Line graph ; Hamiltonian graph ; Supereulerian graph ; Claw-free graph ; DCT graph ; P3D graph ; Collapsible graph
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 June, 2012
• 卷：312
• 期：11
• 页码：1877-1882
• 文件大小：222 K

摘要

Thomassen conjectured that every 4-connected line graph is hamiltonian. It has been proved that every 4-connected line graph of a claw-free graph, or an almost claw-free graph, or a quasi-claw-free graph, is hamiltonian. In 1998, Ainouche et聽al.聽 introduced the class of DCT graphs, which properly contains both the almost claw-free graphs and the quasi-claw-free graphs. Recently, Broersma and Vumar (2009) found another family of graphs, called P3D graphs, which properly contain all quasi-claw-free graphs. In this paper, we investigate the hamiltonicity of 3-connected line graphs of DCT graphs and P3D graphs, and prove that if is a DCT graph or a P3D graph with and if does not have an independent vertex 3-cut, then is hamiltonian. Consequently, every 4-connected line graph of a DCT graph or a P3D graph is hamiltonian.