文摘
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 .