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