## Abstract

We recently proved two new results on the hamiltonicity of almost distance-hereditary graphs, involving implicit degree conditions on claws, i.e., induced subgraphs isomorphic to K_{1,3}. A graph G of order n is called implicit 1-heavy if at least one of the end vertices of each induced claw of G has implicit degree at least n/2, and G is called implicit claw-heavy if each induced claw of G has a pair of end vertices with implicit degree sum at least n. A graph G is said to be almost distance-hereditary if each connected induced subgraph H of G has the property d_{H}(x, y) = d_{G}(x, y) + 1 for any pair of vertices x, y ? V (H). We recently proved that every 2-connected implicit claw-heavy almost distance-hereditary graph is hamiltonian, and that every 3-connected implicit 1-heavy almost distance-hereditary graph is hamiltonian. These results improve two recent results due to Chen and Ning.

Original language | English |
---|---|

Pages | 179-182 |

Number of pages | 4 |

Publication status | Published - 2019 |

Event | 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - CNAM, Paris, France Duration: 18 Jun 2018 → 20 Jun 2018 Conference number: 16 http://ctw18.lipn.univ-paris13.fr/ |

### Workshop

Workshop | 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 |
---|---|

Abbreviated title | CTW 2018 |

Country/Territory | France |

City | Paris |

Period | 18/06/18 → 20/06/18 |

Internet address |

## Keywords

- (almost) distance-hereditary graph
- Claw-heavy
- Hamilton cycle
- Implicit degree
- Induced claw