کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8941824 | 1645038 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On some open problems concerning quorum colorings of graphs
ترجمه فارسی عنوان
در برخی از مشکلات باز در مورد رنگ آمیزی نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی کوروم، اتحادهای دفاعی، پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A partition Ï={V1,V2,â¦,Vk} of the vertex set V of a graph G into k color classes Vi, with iâ{1,â¦,k}, is called a quorum coloring if, for every vertex vâV, at least half of the vertices in the closed neighborhood N[v] of v have the same color as v. The maximum order of a quorum coloring of G is called the quorum coloring number of G and is denoted Ïq(G). In this paper, we give answers to three open problems stated in 2013 by Hedetniemi, Hedetniemi, Laskar and Mulder. In particular, we show that the decision problem associated with Ïq(G) is NP-complete, and we prove that for any graph G on n vertices, Ïq(G)+Ïq(G¯)â¤n+2, where G¯ is the complement of G.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 294-299
Journal: Discrete Applied Mathematics - Volume 247, 1 October 2018, Pages 294-299
نویسندگان
Rafik Sahbi, Mustapha Chellali,