کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646548 1413648 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Acyclicity in edge-colored graphs
ترجمه فارسی عنوان
غیرچرخه‌ای بودن در نمودارهای لبه رنگی
کلمات کلیدی
نمودار لبه رنگی ؛پیاده روی به درستی رنگی شده؛ پیاده روی بسته؛ دنباله بسته؛ غیرقابل چرخش
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A walk WW in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in WW is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type ii is a proper superset of graphs of acyclicity of type i+1i+1, i=1,2,3,4.i=1,2,3,4. The first three types are equivalent to the absence of PC cycles, PC closed trails, and PC closed walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex-disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 1–8
نویسندگان
, , , , ,