کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902862 | 1632394 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extremal problems on the Hamiltonicity of claw-free graphs
ترجمه فارسی عنوان
مشکلات افراطی در همیلتینیت گراف های بدون نقص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چرخه همیلتون، نمودار بدون چنگال، تعداد کلک، بسته شدن بدون کلاه، مقادیر ویژه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In 1962, ErdÅs proved that if a graph G with n vertices satisfies e(G)>maxnâk2+k2,â(n+1)â2â2+nâ122,where the minimum degree δ(G)â¥k and 1â¤kâ¤(nâ1)â2, then it is Hamiltonian. For nâ¥2k+1, let Enk=Kkâ¨(kK1+Knâ2k), where “⨔ is the “join” operation. One can observe e(Enk)=nâk2+k2 and Enk is not Hamiltonian. As Enk contains induced claws for kâ¥2, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of ErdÅs' theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include RyjáÄek's claw-free closure theory and Brousek's characterization of minimal 2-connected claw-free non-Hamiltonian graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 10, October 2018, Pages 2774-2788
Journal: Discrete Mathematics - Volume 341, Issue 10, October 2018, Pages 2774-2788
نویسندگان
Binlong Li, Bo Ning, Xing Peng,