On defensive alliances and strong global offensive alliances ?
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 G G and a given integer a a , whether G G contains a defensive alliance of order at most a a . Furthermore, we prove that determining the strong global offensive alliance number ? o  ( G ) of a graph G G is APX-hard for cubic graphs and NP-hard for chordal graphs. For a graph G G of minimum degree at least 2, we prove ? o  ( G ) ? 3 n ( G ) / 4 , which improves previous results by Favaron et al. and Sigarreta and Rodrguez. Finally, we prove ? o  ( G ) ? ( 1 2 + ( 1 + o ( ? ( G ) ) ) ln ( ? ( G ) + 1 ) ? ( G ) + 1 ) n ( G ) .
defensive alliance strong global offensive alliance