Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648038 | Discrete Mathematics | 2012 | 6 Pages |
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. [2] 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) [5] 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 GG is a DCT graph or a P3D graph with κ(L(G))≥3κ(L(G))≥3 and if L(G)L(G) does not have an independent vertex 3-cut, then L(G)L(G) is hamiltonian. Consequently, every 4-connected line graph of a DCT graph or a P3D graph is hamiltonian.