## Abstract

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 G is a DCT graph or a P3D graph with κ(L(G))<3 and if L(G) does not have an independent vertex 3-cut, then L(G) is hamiltonian. Consequently, every 4-connected line graph of a DCT graph or a P3D graph is hamiltonian.

Original language | English (US) |
---|---|

Pages (from-to) | 1877-1882 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 312 |

Issue number | 11 |

DOIs | |

State | Published - Jun 6 2012 |

Externally published | Yes |

## Keywords

- Claw-free graph
- Collapsible graph
- DCT graph
- Hamiltonian graph
- Line graph
- P3D graph
- Supereulerian graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics