<p>A function <i>f</i> that assigns values from the set <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{0, 1, 2\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> to each vertex of a graph <i>G</i> is called a 2-rainbow independent dominating function, if the vertices assigned the value 1 form an independent set, the vertices assigned the value 2 form another independent set, and every vertex to which 0 is assigned has at least one neighbor in each of the mentioned independent sets. The weight of this function is the total number of vertices assigned nonzero values. The 2-rainbow independent domination number of <i>G</i>, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _{\textrm{ri}2}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mtext>ri</mtext> <mn>2</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the minimum weight of such a function. Motivated by a real-life application, we study the 2-rainbow independent domination number of the complementary prism <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">\(G \overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mover> <mi>G</mi> <mo>¯</mo> </mover> </mrow> </math></EquationSource> </InlineEquation> of a graph <i>G</i>, which is constructed by taking <i>G</i> and its complement <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq4.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>G</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation>, and then adding edges between corresponding vertices. We provide tight bounds for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">\(\gamma _{\textrm{ri}2}(G\overline{G})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mtext>ri</mtext> <mn>2</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and characterize graphs for which the lower bound, i.e. <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3189_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="181" /> </InlineMediaObject> <EquationSource Format="TEX">\(\max \{\gamma _{\textrm{ri}2}(G), \gamma _{\textrm{ri}2}(\overline{G})\}+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <msub> <mi>γ</mi> <mrow> <mtext>ri</mtext> <mn>2</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <msub> <mi>γ</mi> <mrow> <mtext>ri</mtext> <mn>2</mn> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, is attained. The obtained results can, in practice, enable the prediction of the cost estimate for a given communication or surveillance network.</p>

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

2-rainbow independent domination in complementary prisms

  • Dragana Božović,
  • Gordana Radić,
  • Aleksandra Tepeh

摘要

A function f that assigns values from the set \(\{0, 1, 2\}\) { 0 , 1 , 2 } to each vertex of a graph G is called a 2-rainbow independent dominating function, if the vertices assigned the value 1 form an independent set, the vertices assigned the value 2 form another independent set, and every vertex to which 0 is assigned has at least one neighbor in each of the mentioned independent sets. The weight of this function is the total number of vertices assigned nonzero values. The 2-rainbow independent domination number of G, \(\gamma _{\textrm{ri}2}(G)\) γ ri 2 ( G ) , is the minimum weight of such a function. Motivated by a real-life application, we study the 2-rainbow independent domination number of the complementary prism \(G \overline{G}\) G G ¯ of a graph G, which is constructed by taking G and its complement \(\overline{G}\) G ¯ , and then adding edges between corresponding vertices. We provide tight bounds for \(\gamma _{\textrm{ri}2}(G\overline{G})\) γ ri 2 ( G G ¯ ) , and characterize graphs for which the lower bound, i.e. \(\max \{\gamma _{\textrm{ri}2}(G), \gamma _{\textrm{ri}2}(\overline{G})\}+1\) max { γ ri 2 ( G ) , γ ri 2 ( G ¯ ) } + 1 , is attained. The obtained results can, in practice, enable the prediction of the cost estimate for a given communication or surveillance network.