Sufficient degree conditions for traceability of claw-free graphs

Tao Tian, Hajo Broersma, Liming Xiong

Research output: Contribution to conferencePaperAcademicpeer-review

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(2n14-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 languageEnglish
Pages164-167
Number of pages4
Publication statusPublished - 2019
Event16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - CNAM, Paris, France
Duration: 18 Jun 201820 Jun 2018
Conference number: 16
http://ctw18.lipn.univ-paris13.fr/

Workshop

Workshop16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018
Abbreviated titleCTW 2018
Country/TerritoryFrance
CityParis
Period18/06/1820/06/18
Internet address

Keywords

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

Fingerprint

Dive into the research topics of 'Sufficient degree conditions for traceability of claw-free graphs'. Together they form a unique fingerprint.

Cite this