Global Offensive Alliances and Groupies in Heterogeneous Random Graphs

Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>γ</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:math> . 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> of order n with an individual probability $$p_n(e)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> independently. For a complete t -ary tree T with height 2, $$\gamma _T=\eta _T=t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mi>T</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>T</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> . In the random graph setting, it is found that $$\gamma _G\asymp \eta _G\asymp n/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mo>≍</mml:mo> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mo>≍</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> under some neighborhood density conditions of the edge probabilities, where $$a_n\asymp b_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>≍</mml:mo> <mml:msub> <mml:mi>b</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> means $$a_n/b_n\rightarrow 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>/</mml:mo> <mml:msub> <mml:mi>b</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>→</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> as $$n\rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> .