کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949573 1440194 2017 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
ترجمه فارسی عنوان
یک شرایط کافی جدید برای وجود چرخه متناوب هامیلتونی در چند گراف چند لبه
کلمات کلیدی
سیکل همیلتون چرخه همیلتون متناوب، چند تصویر چند لبه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , ,