On defensive alliances and strong global offensive alliances

详细信息    查看全文

• 作者：Mitre C. Dourado ; Luerbio Faria ; Miguel A. Piza帽a ; Dieter Rautenbach ; Jayme L. Szwarcfiter
• 关键词：Defensive alliance ; Strong global offensive alliance
• 刊名：Discrete Applied Mathematics
• 出版年：30 January, 2014
• 年：2014
• 卷：163
• 期：part_P2
• 页码：136-141
• 全文大小：415 K

文摘

We consider complexity issues and upper bounds for defensive alliances and strong global offensive alliances in graphs. We prove that it is NP-complete to decide for a given 6-regular graph and a given integer , whether contains a defensive alliance of order at most . Furthermore, we prove that determining the strong global offensive alliance number of a graph is APX-hard for cubic graphs and NP-hard for chordal graphs. For a graph of minimum degree at least 2, we prove , which improves previous results by Favaron et al. and Sigarreta and Rodr铆guez. Finally, we prove .