Partitioning a Graph into Global Powerful k-Alliances

摘要

A set S of vertices of a graph is a defensive k-alliance if every vertex ${vin S}$ has at least k more neighbors in S than it has outside of S. Analogously, a set S is an offensive k-alliance if every vertex in the neighborhood of S has at least k more neighbors in S than it has outside of S. Also, a powerful k-alliance is a set S of vertices of the graph, which is both defensive k-alliance and offensive (k + 2)-alliance. A powerful k-alliance is called global if it is a dominating set. In this paper we show that for k ≥ 0, no graph is partitionable into global powerful k-alliances and, for k ≤ −1, we obtain upper bounds on the maximum number of sets belonging to a partition of a graph into global powerful k-alliances. In addition, we study the close relationships that exist between partitions of a Cartesian product graph, Γ1 × Γ2, into (global) powerful (k 1 + k 2)-alliances and partitions of Γ i into (global) powerful k i -alliances, ${iin {1,2}}$ .