A defensive k-alliance in a graph is a set S of vertices with the property that every vertex in S has at least k more neighbors in S than it has outside of S. A defensive k-alliance S is called global if it forms a do...A defensive k-alliance in a graph is a set S of vertices with the property that every vertex in S has at least k more neighbors in S than it has outside of S. A defensive k-alliance S is called global if it forms a dominating Set. In this paper we study the problem of partitioning the vertex set of a graph into （global） defensive k-alliances. The （global） defensive k-alliance partition number of a graph Г = （V, E）, ψkgd（F）） ψkd（F）, is defined to be the maximum number of sets in a partition of V such that each set is a （global） defensive k-alliance. We obtain tight bounds on ψkd（F） and ψkgd（F） in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of F1 × F2 into （global） defensive （kl ＋ k2）-alliances and partitions of Fi into （global） defensive ki-alliances, i ∈ {1, 2}.展开更多
A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-a...A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.展开更多
文摘A defensive k-alliance in a graph is a set S of vertices with the property that every vertex in S has at least k more neighbors in S than it has outside of S. A defensive k-alliance S is called global if it forms a dominating Set. In this paper we study the problem of partitioning the vertex set of a graph into （global） defensive k-alliances. The （global） defensive k-alliance partition number of a graph Г = （V, E）, ψkgd（F）） ψkd（F）, is defined to be the maximum number of sets in a partition of V such that each set is a （global） defensive k-alliance. We obtain tight bounds on ψkd（F） and ψkgd（F） in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of F1 × F2 into （global） defensive （kl ＋ k2）-alliances and partitions of Fi into （global） defensive ki-alliances, i ∈ {1, 2}.
文摘A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.
