کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949502 | 1440192 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colorful edge decomposition of graphs: Some polynomial cases
ترجمه فارسی عنوان
تجزیه لبه رنگی گراف: برخی موارد چند جملهای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تجزیه لبه رنگارنگ، جعبه رنگ نقاشی، تجزیه گراف، ماتریس کاملا متحرک، الگوریتم چندجمله ای،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this work, we investigate some properties of this edge decomposition. We prove that for each t, every tree has a colorful t-edge decomposition and that decomposition can be found in polynomial time. On the negative side, we prove that for a given graph G with 2â¤Î´(G)â¤Î(G)â¤3 determining whether G has a colorful 2-edge decomposition is NP-complete. Among other results, we show that for a given bipartite graph G with degree set {a1,a2,â¦,ac} where c is a constant number, if for each i, 1â¤iâ¤c, the induced subgraph on the set of vertices of degree ai has d connected components, where d is a constant number, then there is a polynomial time algorithm to decide whether G has a colorful 2-edge decomposition. Also, we prove that every r-regular graph G with at most one cut edge has a colorful 2-edge decomposition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 155-165
Journal: Discrete Applied Mathematics - Volume 231, 20 November 2017, Pages 155-165
نویسندگان
Ali Dehghan, Mohammad-Reza Sadeghi,