Global offensive alliances in graphs and random graphs

A global offensive alliance in a graph G=(V,E)G=(V,E) is a subset SS of VV such that for every vertex vv not in SS at least half of the vertices in the closed neighborhood of vv are in SS. The cardinality of a minimum size global offensive alliance in GG is called the global offensive alliance number of GG. We give an upper bound on the global (strong) offensive alliance number of a graph in terms of its degree sequence. We also study global offensive alliances of random graphs. In particular, it is proved that if p(logn)1/2→∞p(logn)1/2→∞ then with high probability G(n,p)G(n,p) has a global offensive alliance of size at most cncn if c>1/2c>1/2 and no global offensive alliance of size at most cncn if c<1/2c<1/2.