Partitioning a graph into offensive image-alliances Original Research Article

An offensive image-alliance in a graph is a set image of vertices with the property that every vertex in the boundary of image has at least image more neighbors in image than it has outside of image. An offensive image-alliance image 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 image-alliances. The (global) offensive image-alliance partition number of a graph image, denoted by (image) image, is defined to be the maximum number of sets in a partition of image such that each set is an offensive (a global offensive) image-alliance. We show that image if image is a graph without isolated vertices and image. Moreover, we show that if image is partitionable into global offensive image-alliances for image, then image. As a consequence of the study we show that the chromatic number of image is at most 3 if image. In addition, for image, we obtain tight bounds on image and image 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 image, for image, where image denotes the maximum degree of image, and image, for image.