کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328286 | 683918 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Partitioning a graph into offensive k-alliances
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Partitioning a graph into offensive k-alliances Partitioning a graph into offensive k-alliances](/preview/png/10328286.png)
چکیده انگلیسی
An offensive k-alliance in a graph is a set S of vertices with the property that every vertex in the boundary of S has at least k more neighbors in S than it has outside of S. An offensive k-alliance S is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) offensive k-alliances. The (global) offensive k-alliance partition number of a graph Î=(V,E), denoted by (Ïkgo(Î)) Ïko(Î), is defined to be the maximum number of sets in a partition of V such that each set is an offensive (a global offensive) k-alliance. We show that 2â¤Ïkgo(Î)â¤3âk if Î is a graph without isolated vertices and kâ{2âÎ,...,0}. Moreover, we show that if Î is partitionable into global offensive k-alliances for kâ¥1, then Ïkgo(Î)=2. As a consequence of the study we show that the chromatic number of Î is at most 3 if Ï0go(Î)=3. In addition, for kâ¤0, we obtain tight bounds on Ïko(Î) and Ïkgo(Î) in terms of several parameters of the graph including the order, size, minimum and maximum degree. Finally, we study the particular case of the cartesian product of graphs, showing that Ïko(Î1ÃÎ2)â¥Ïk1o(Î1)Ïk2o(Î2), for kâ¤min{k1âÎ2,k2âÎ1}, where Îi denotes the maximum degree of Îi, and Ïkgo(Î1ÃÎ2)â¥max{Ïk1go(Î1),Ïk2go(Î2)}, for kâ¤min{k1,k2}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 4, 28 February 2011, Pages 224-231
Journal: Discrete Applied Mathematics - Volume 159, Issue 4, 28 February 2011, Pages 224-231
نویسندگان
José M. Sigarreta, Ismael G. Yero, Sergio Bermudo, Juan A. RodrÃguez-Velázquez,