Alliance free sets in Cartesian product graphs

Let G=(V,E)G=(V,E) be a graph. For a non-empty subset of vertices S⊆VS⊆V, and vertex v∈Vv∈V, let δS(v)=|{u∈S:uv∈E}|δS(v)=|{u∈S:uv∈E}| denote the cardinality of the set of neighbors of vv in SS, and let S¯=V−S. Consider the following condition: equation(1)δS(v)≥δS¯(v)+k, which states that a vertex vv has at least kk more neighbors in SS than it has in S¯. A set S⊆VS⊆V that satisfies Condition (1) for every vertex v∈Sv∈S is called a defensive  kk-alliance   and for every vertex vv in the open neighborhood of SS is called an offensive  kk-alliance  . A subset of vertices S⊆VS⊆V is a powerful  kk-alliance   if it is both a defensive kk-alliance and an offensive (k+2)(k+2)-alliance. Moreover, a subset X⊂VX⊂V is a defensive (an offensive or a powerful) kk-alliance free set if XX does not contain any defensive (offensive or powerful, respectively) kk-alliance. In this article we study the relationships between defensive (offensive, powerful) kk-alliance free sets in Cartesian product graphs and defensive (offensive, powerful) kk-alliance free sets in the factor graphs.