Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328286 | Discrete Applied Mathematics | 2011 | 8 Pages |
Abstract
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}.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
José M. Sigarreta, Ismael G. Yero, Sergio Bermudo, Juan A. RodrÃguez-Velázquez,