Partitioning a Graph into Defensive k-Alliances

作     者：Ismael G.YERO Sergio BERMUDO Juan A.RODRiGUEZ-VELAZQUEZ Jose M.SIGARRETA 

作者机构：Department of Computer Engineering and MathematicsRovira i Virgili UniversityAv.Pai'sos Catalans 2643007 TarragonaSpain Department of EconomyQuantitative Methods and Economic HistoryPablo de Olavide UniversityCarretera de Utrera Kin.141013-SevillaSpain Department of Computer Engineering and MathematicsRovira i Virgili UniversityAv.Paisos Catalans 2643007 TarragonaSpain Faculty of MathematicsAutonomous University of GuerreroCarlos E.Adame 5Co1.La GaritaAcapulcoGuerreroMexico 

出 版 物：《Acta Mathematica Sinica,English Series》 (数学学报（英文版）)

年 卷 期：2011年第27卷第1期

页      面：73-82页

核心收录：

学科分类：0821[工学-纺织科学与工程] 07[理学] 08[工学] 070104[理学-应用数学] 082104[工学-服装设计与工程] 0701[理学-数学] 

基　　金：Spanish Ministry of Science and Innovation through Projects CONSOLIDER INGENIO Rovira i Virgili University through Project Junta de Andalucia 

主　　题：Defensive alliances dominating sets domination isoperimetric number 

摘      要：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}.