کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418476 681673 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian cycles in spanning subgraphs of line graphs
ترجمه فارسی عنوان
چرخه هامیلتونی در زیرگراف‌های پوشای نمودارهای خطی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, , , ,