## Abstract

We present new results on the traceability of claw-free graphs. In particular, we consider sufficient minimum degree and degree sum conditions that imply that these graphs admit a Hamilton path, unless they have a small order or they belong to well-defined classes of exceptional graphs. Our main result implies that a 2-connected claw-free graph G of sufficiently large order n with minimum degree d(G) = 22 is traceable if the degree sum of any set of t independent vertices of G is at least ^{t}(2^{n}_{14}^{-}^{5)} , where t ? {1, 2, . . ., 7}, unless G belongs to one of a number of well-defined classes of exceptional graphs depending on t. Our results also imply that a 2-connected claw-free graph G of sufficiently large order n with d(G) = 18 is traceable if the degree sum of any set of six independent vertices is larger than n - 6, and that this lower bound on the degree sums is sharp.

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

Pages | 164-167 |

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

- Claw-free graph
- Closure
- Line graph
- Spanning trail
- Traceable graph