کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949573 | 1440194 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
ترجمه فارسی عنوان
یک شرایط کافی جدید برای وجود چرخه متناوب هامیلتونی در چند گراف چند لبه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سیکل همیلتون چرخه همیلتون متناوب، چند تصویر چند لبه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A path (cycle) in a c-edge-colored multigraph is alternating if no two consecutive edges have the same color. The problem of determining the existence of alternating Hamiltonian paths and cycles in 2-edge-colored multigraphs is NP-complete (Gorbenko and Popov, 2012) and it has been studied by several authors. Given a 2-colored multigraph G, an alternating 3-path P=(x1,x2,x3,x4) is closed-alternating if there exist y, wâV(G) such that C=(x1,y,w,x4,x1) is an alternating cycle. Furthermore, G is closed-alternating whenever each alternating 3-path is closed-alternating. In this work, we prove that if G is connected, closed-alternating and it has an alternating cycle factor (i.e., a collection of vertex-disjoint alternating cycles that covers all the vertices), then G has an alternating Hamiltonian cycle.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 55-63
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 55-63
نویسندگان
Alejandro Contreras-Balbuena, Hortensia Galeana-Sánchez, Ilan A. Goldfeder,