<p>Let <i>G</i>,&#xa0;<i>H</i> be graphs. A set <i>I</i> of vertices of <i>G</i> is called an <i>H</i>-isolating set of <i>G</i> if <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\(G-N[I]\)</EquationSource> </InlineEquation> contains no copies of <i>H</i>, where <i>N</i>[<i>I</i>] is the closed neighborhood of <i>I</i>. The cardinality of a minimum <i>H</i>-isolating set in <i>G</i> is called the <i>H</i>-isolation number of <i>G</i> and is denoted by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\iota (G,H)\)</EquationSource> </InlineEquation>. Zhang and Wu (Discrete Appl Math 357:99–111, 2024) proved that, given a connected graph <i>H</i>, for any graph <i>G</i> with exactly <i>s</i> components, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq3.gif" Format="GIF" Height="28" Rendition="HTML" Resolution="72" Type="Linedraw" Width="163" /> </InlineMediaObject> <EquationSource Format="TEX">\(\iota (G,H)\le \gamma (H)\frac{m(G)+s}{m(H)+1}\)</EquationSource> </InlineEquation>, where <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (H)\)</EquationSource> </InlineEquation> is the domination number of <i>H</i>, and <i>m</i>(<i>G</i>) and <i>m</i>(<i>H</i>) are the respective sizes of <i>G</i> and <i>H</i>. Then, they conjectured that, given a graph <i>H</i> with <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (H)=1\)</EquationSource> </InlineEquation>, for any connected graph <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq6.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\ne H\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq7.gif" Format="GIF" Height="28" Rendition="HTML" Resolution="72" Type="Linedraw" Width="125" /> </InlineMediaObject> <EquationSource Format="TEX">\(\iota (G,H)\le \frac{m(G)+1}{m(H)+2}\)</EquationSource> </InlineEquation>. Borg (Discrete Appl Math 371:247–253, 2025) proved the conjecture. In this paper, we prove that, given a connected graph <i>H</i> with <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (H)\ge 2\)</EquationSource> </InlineEquation>, for any graph <i>G</i>, <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq9.gif" Format="GIF" Height="28" Rendition="HTML" Resolution="72" Type="Linedraw" Width="198" /> </InlineMediaObject> <EquationSource Format="TEX">\(\iota (G,H)\le \gamma (H)\frac{m(G)}{m(H)+\gamma (H)+1}\)</EquationSource> </InlineEquation> with equality if and only if <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(H=P_4\)</EquationSource> </InlineEquation> and every component of <i>G</i> is <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_4\)</EquationSource> </InlineEquation>. The result is a natural extension of Borg’s one and an improvement of Zhang and Wu’s one for <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2946_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma (H)\ge 2\)</EquationSource> </InlineEquation>. Several problems are posed.</p>

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

Isolation of Connected Graphs in Terms of Size

  • Ayman El Zein,
  • Manar Shreif

摘要

Let GH be graphs. A set I of vertices of G is called an H-isolating set of G if \(G-N[I]\) contains no copies of H, where N[I] is the closed neighborhood of I. The cardinality of a minimum H-isolating set in G is called the H-isolation number of G and is denoted by \(\iota (G,H)\) . Zhang and Wu (Discrete Appl Math 357:99–111, 2024) proved that, given a connected graph H, for any graph G with exactly s components, \(\iota (G,H)\le \gamma (H)\frac{m(G)+s}{m(H)+1}\) , where \(\gamma (H)\) is the domination number of H, and m(G) and m(H) are the respective sizes of G and H. Then, they conjectured that, given a graph H with \(\gamma (H)=1\) , for any connected graph \(G\ne H\) , \(\iota (G,H)\le \frac{m(G)+1}{m(H)+2}\) . Borg (Discrete Appl Math 371:247–253, 2025) proved the conjecture. In this paper, we prove that, given a connected graph H with \(\gamma (H)\ge 2\) , for any graph G, \(\iota (G,H)\le \gamma (H)\frac{m(G)}{m(H)+\gamma (H)+1}\) with equality if and only if \(H=P_4\) and every component of G is \(P_4\) . The result is a natural extension of Borg’s one and an improvement of Zhang and Wu’s one for \(\gamma (H)\ge 2\) . Several problems are posed.