Global Offensive Alliances and Groupies in Heterogeneous Random Graphs

A vertex subset S of a graph G is a global offensive alliance if every non-member v of S has at least as many neighbors inside S as outside S in the closed neighborhood of v. The global offensive alliance number $$\gamma _G$$ γ G is the cardinality of a minimal global offensive alliance. A vertex is a groupie if its degree is not less than the mean of the degrees of its neighbors. The number of groupies in G is denoted by $$\eta _G$$ η G . In this paper, we study these two sort of orthogonal concepts over a heterogenous random graph G obtained by including each edge e from a complete graph $$K_n$$ K n of order n with an individual probability $$p_n(e)$$ p n ( e ) independently. For a complete t-ary tree T with height 2, $$\gamma _T=\eta _T=t$$ γ T = η T = t . In the random graph setting, it is found that $$\gamma _G\asymp \eta _G\asymp n/2$$ γ G ≍ η G ≍ n / 2 under some neighborhood density conditions of the edge probabilities, where $$a_n\asymp b_n$$ a n ≍ b n means $$a_n/b_n\rightarrow 1$$ a n / b n → 1 as $$n\rightarrow \infty $$ n → ∞ .