Offensive image-alliances in graphs Original Research Article

Let image be a simple graph. For a nonempty set image, and a vertex image denotes the number of neighbors image has in image. A nonempty set image is an offensive image-alliance in image if image, where image denotes the boundary of image. An offensive image-alliance image is called global if it forms a dominating set. The global offensive image-alliance number of image, denoted by image, is the minimum cardinality of a global offensive image-alliance in image. We show that the problem of finding optimal (global) offensive image-alliances is NP-complete and we obtain several tight bounds on image.