Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420549 | Discrete Applied Mathematics | 2009 | 9 Pages |
Abstract
In this paper, we obtain several tight bounds of the defensive kk-alliance number in the complement graph from other parameters of the graph. In particular, we investigate the relationship between the alliance numbers of the complement graph and the minimum and maximum degree, the domination number and the isoperimetric number of the graph. Moreover, we prove the NP-completeness of the decision problem underlying the defensive kk-alliance number.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J.M. Sigarreta, S. Bermudo, H. Fernau,