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 K1,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 dH(x, y) = dG(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