<p>A vertex subset <i>S</i> of a graph <i>G</i> is a global offensive alliance if every non-member <i>v</i> of <i>S</i> has at least as many neighbors inside <i>S</i> as outside <i>S</i> in the closed neighborhood of <i>v</i>. The global offensive alliance number <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _G\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mi>G</mi> </msub> </math></EquationSource> </InlineEquation> 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 <i>G</i> is denoted by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq2.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(\eta _G\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>η</mi> <mi>G</mi> </msub> </math></EquationSource> </InlineEquation>. In this paper, we study these two sort of orthogonal concepts over a heterogenous random graph <i>G</i> obtained by including each edge <i>e</i> from a complete graph <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> of order <i>n</i> with an individual probability <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(p_n(e)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>p</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> independently. For a complete <i>t</i>-ary tree <i>T</i> with height 2, <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="90" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _T=\eta _T=t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mi>T</mi> </msub> <mo>=</mo> <msub> <mi>η</mi> <mi>T</mi> </msub> <mo>=</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>. In the random graph setting, it is found that <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="112" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _G\asymp \eta _G\asymp n/2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mi>G</mi> </msub> <mo>≍</mo> <msub> <mi>η</mi> <mi>G</mi> </msub> <mo>≍</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> under some neighborhood density conditions of the edge probabilities, where <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(a_n\asymp b_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mi>n</mi> </msub> <mo>≍</mo> <msub> <mi>b</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> means <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\(a_n/b_n\rightarrow 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>a</mi> <mi>n</mi> </msub> <mo stretchy="false">/</mo> <msub> <mi>b</mi> <mi>n</mi> </msub> <mo stretchy="false">→</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> as <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11009_2025_10151_Article_IEq9.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\rightarrow \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Global Offensive Alliances and Groupies in Heterogeneous Random Graphs

  • Yilun Shang

摘要

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 .