کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647935 1342383 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Closure, clique covering and degree conditions for Hamilton-connectedness in claw-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Closure, clique covering and degree conditions for Hamilton-connectedness in claw-free graphs
چکیده انگلیسی

We strengthen the closure concept for Hamilton-connectedness in claw-free graphs, introduced by the second and fourth authors, such that the strong closure GMGM of a claw-free graph GG is the line graph of a multigraph containing at most two triangles or at most one double edge.Using the concept of strong closure, we prove that a 3-connected claw-free graph GG is Hamilton-connected if GG satisfies one of the following: (i) GG can be covered by at most 5 cliques, (ii) δ(G)≥4δ(G)≥4 and GG can be covered by at most 6 cliques, (iii) δ(G)≥6δ(G)≥6 and GG can be covered by at most 7 cliques.Finally, by reconsidering the relation between degree conditions and clique coverings in the case of the strong closure GMGM, we prove that every 3-connected claw-free graph GG of minimum degree δ(G)≥24δ(G)≥24 and minimum degree sum σ8(G)≥n+50σ8(G)≥n+50 (or, as a corollary, of order n≥142n≥142 and minimum degree δ(G)≥n+508) is Hamilton-connected.We also show that our results are asymptotically sharp.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 14, 28 July 2012, Pages 2177–2189
نویسندگان
, , , ,