Jun 14, 2018: Tao Tian: Sufficient degree conditions for traceability of claw-free graphs

June 14, 2018Sufficient degree conditions for traceability of claw-free graphs
Room: RA 3231Tao Tian
15:45-16:45

In this talk, we are mainly interested in degree and neighborhood conditions for traceability of 2-connected claw-free graphs, motivated by recent results on counterparts for hamiltonicity, and in an attempt to unify several existing results. 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 more than or equals to 22 is traceable if the degree sum of any set of t independent vertices of G is at least t(2n-5) /14, 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 minimum degree more than or equals to 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.