Alliance free sets in Cartesian product graphs

作者：Yero Ismael G; Rodriguez Velazquez Juan A^*; Bermudo Sergio

来源：Discrete Applied Mathematics, 2013, 161(10-11): 1618-1625.

DOI：10.1016/j.dam.2013.01.011

• Defensive alliance
• Offensive alliance
• Alliance free set
• Cartesian product graphs

Let G = (V, E) be a graph. For a non-empty subset of vertices S c V. and vertex V E V. let delta(S)(v) = vertical bar{u is an element of S: uv is an element of E}vertical bar denote the cardinality of the set of neighbors of v in S, and let S = V - S. Consider the following condition: %26lt;br%26gt;delta S(v) %26gt;= delta((S) over bar)(v) + k, (1) %26lt;br%26gt;which states that a vertex v has at least k more neighbors in S than it has in (S) over bar. A set S subset of V that satisfies Condition (I) for every vertex v is an element of S is called a defensive k-alliance and for every vertex v in the open neighborhood of S is called an offensive k-alliance. A subset of vertices S subset of V is a powerful k-alliance if it is both a defensive k-alliance and an offensive (k + 2)-alliance. Moreover, a subset X subset of 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.

• 出版日期2013-7