کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418476 | 681673 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hamiltonian cycles in spanning subgraphs of line graphs
ترجمه فارسی عنوان
چرخه هامیلتونی در زیرگرافهای پوشای نمودارهای خطی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چرخه هامیلتونی؛ نمودار خط؛ زیرگراف پوشا
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let GG be a graph and e=uve=uv an edge in GG (also a vertex in the line graph L(G)L(G) of GG). Then ee is in two cliques EG(u)EG(u) and EG(v)EG(v) with EG(u)∩EG(v)={e}EG(u)∩EG(v)={e} of L(G)L(G), that correspond to all edges incident with uu and vv in GG respectively. Let SL(G)SL(G) be any spanning subgraph of L(G)L(G) such that every vertex e=uve=uv is adjacent to at least min{dG(u)−1,⌈34dG(u)+12⌉} vertices of EG(u)EG(u) and to at least min{dG(v)−1,⌈34dG(v)+12⌉} vertices of EG(v)EG(v). Then if L(G)L(G) is Hamiltonian, we show that SL(G)SL(G) is Hamiltonian. As a corollary we obtain a lower bound on the number of edge-disjoint Hamiltonian cycles in L(G)L(G).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 287–295
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 287–295
نویسندگان
Hao Li, Weihua He, Weihua Yang, Yandong Bai,