کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418472 | 681673 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sufficient conditions for 2-rainbow connected graphs
ترجمه فارسی عنوان
شرایط کافی برای نمودارهای متصل رنگین کمان 2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی رنگین کمان؛ متصل به رنگین کمان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An edge-coloured connected graph GG is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses kk colours then GG is called kk-rainbow connected. The rainbow connection number of GG, denoted by rc(G), is the minimum kk such that GG is kk-rainbow connected. Even the problem to decide whether rc(G)=2 is NP-complete. It has been shown that if GG is a connected graph of order nn and size mm with n−22+2≤m≤n−12, then 2≤rc(G)≤3.In this paper we will present sufficient conditions for graphs GG of this size to fulfil rc(G)=2 depending on vertex degrees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 247–250
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 247–250
نویسندگان
Arnfried Kemnitz, Ingo Schiermeyer,