2011/12/09 by Ismael G. Yero, Yero, Ismael G., Juan A. Rodriguez-Velazquez +3
Mathematics · #05C69 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69 #msc:05C70
paper · pdf · doi:10.48550/arxiv.1112.2068
arxiv created 2011/12/09 · arxiv updated 2011/12/12
Let G=(V,E) be a graph. For a non-empty subset of vertices S⊆ V, and vertex v∈ V, let δS(v)=|\u∈ S:uv∈ E\| denote the cardinality of the set of neighbors of v in S, and let S=V-S. Consider the following condition: equation δS(v)≥ δ_S(v)+k, \equation which states that a vertex v has at least k more neighbors in S than it has in S. A set S⊆ V that satisfies Condition (\refalliancecondition) for every vertex v ∈ S is called a defensive k-alliance; for every vertex v in the neighborhood of S is called an offensive k-alliance. A subset of vertices S⊆ V, is a powerful k-alliance if it is both a defensive k-alliance and an offensive (k +2)-alliance. Moreover, a subset X⊂ V is a defensive (an offensive or a powerful) k-alliance free set if X does not contain any defensive (offensive or powerful, respectively) k-alliance. In this article we study the relationships between defensive (offensive, powerful) k-alliance free sets in Cartesian product graphs and defensive (offensive, powerful) k-alliance free sets in the factor graphs.