کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434541 | 689754 | 2013 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Further hardness results on the rainbow vertex-connection number of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A vertex-colored graph G is rainbow vertex-connected if any pair of vertices in G are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In a previous paper we showed that it is NP-Complete to decide whether a given graph G has rvc(G)=2. In this paper we show that for every integer k≥2, deciding whether rvc(G)≤k is NP-Hard. We also show that for any fixed integer k≥2, this problem belongs to NP-class, and so it becomes NP-Complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 481, 15 April 2013, Pages 18-23
Journal: Theoretical Computer Science - Volume 481, 15 April 2013, Pages 18-23