کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8941830 | 1645038 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the number of maximal independent sets in minimum colorings of split graphs
ترجمه فارسی عنوان
در تعداد مجموعه های حداکثر مستقل در حداقل رنگ از نمودارهای تقسیم شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The largest number of color classes that are dominating sets (or, equivalently, maximal independent sets) among all Ï(G)-colorings of a graph G is called the dominating-Ï-color number of G, and denoted dÏ(G). It was shown in Arumugam et al. (2011) that determining whether dÏ(G)â¥2 is NP-complete even in 3-chromatic graphs G. In this note, we prove that in split graphs the dominating-Ï-color number equals to 1 if and only if its domination number is greater than 2. While such graphs can be efficiently recognized, we prove that for split graphs with domination number at most 2 the decision version of the problem of determining dominating-Ï-color number is NP-complete. We also present existence results for split graphs attaining prescribed values of dominating-Ï-color numbers and some other relevant parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 352-356
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 352-356
نویسندگان
Boštjan Brešar, Nazanin Movarraei,