<p>A subset <i>D</i> of vertices in a graph <i>G</i> is a dominating set if every vertex in <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2024_576_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="74" /> </InlineMediaObject> <EquationSource Format="TEX">\(V(G)\setminus D\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mi>D</mi> </mrow> </math></EquationSource> </InlineEquation> is adjacent to at least one vertex in <i>D</i>. For any positive integer <i>k</i>, a subset <i>S</i> of vertices in <i>G</i> is a <i>k</i>-independent set if <i>G</i>[<i>S</i>] has maximum degree less than <i>k</i>. The <i>k</i>-independence number of <i>G</i>, denoted by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2024_576_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha _k(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>α</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the maximum cardinality of a <i>k</i>-independent set in <i>G</i>. A subset <i>I</i> of vertices in <i>G</i> is a <i>k</i>-independent dominating set if <i>I</i> is both <i>k</i>-independent and dominating. The <i>k</i>-independent domination number of <i>G</i>, denoted by <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2024_576_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(i_k(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>i</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, is the minimum cardinality of a <i>k</i>-independent domination set in <i>G</i>. Recently, Zhang and Wu (J Oper Res Soc China 12:485–494, 2024) showed that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2024_576_Article_IEq4.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">\(i_2(T)\leqslant \frac{2}{3}\alpha _2(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>i</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>⩽</mo> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> <msub> <mi>α</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any nontrivial tree <i>T</i>, and this bound is sharp. In this paper, we give a complete characterization of all trees attaining this bound, which resolves a problem proposed by Zhang and Wu. Moreover, we further prove that <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2024_576_Article_IEq5.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">\(i_3(T)\leqslant \frac{3}{5}\alpha _3(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>i</mi> <mn>3</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>⩽</mo> <mfrac> <mn>3</mn> <mn>5</mn> </mfrac> <msub> <mi>α</mi> <mn>3</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any nontrivial tree <i>T</i>, and characterize all extremal trees for which the equality holds.</p>

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

2-Independence and 3-Independence in Trees

  • Qing Cui,
  • Xu Zou

摘要

A subset D of vertices in a graph G is a dominating set if every vertex in \(V(G)\setminus D\) V ( G ) \ D is adjacent to at least one vertex in D. For any positive integer k, a subset S of vertices in G is a k-independent set if G[S] has maximum degree less than k. The k-independence number of G, denoted by \(\alpha _k(G)\) α k ( G ) , is the maximum cardinality of a k-independent set in G. A subset I of vertices in G is a k-independent dominating set if I is both k-independent and dominating. The k-independent domination number of G, denoted by \(i_k(G)\) i k ( G ) , is the minimum cardinality of a k-independent domination set in G. Recently, Zhang and Wu (J Oper Res Soc China 12:485–494, 2024) showed that \(i_2(T)\leqslant \frac{2}{3}\alpha _2(T)\) i 2 ( T ) 2 3 α 2 ( T ) for any nontrivial tree T, and this bound is sharp. In this paper, we give a complete characterization of all trees attaining this bound, which resolves a problem proposed by Zhang and Wu. Moreover, we further prove that \(i_3(T)\leqslant \frac{3}{5}\alpha _3(T)\) i 3 ( T ) 3 5 α 3 ( T ) for any nontrivial tree T, and characterize all extremal trees for which the equality holds.