<p>A <i>k</i>-rainbow total dominating function of a graph <i>G</i> is a function <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(f: V(G) \rightarrow 2^{[k]}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo>:</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">→</mo> <msup> <mn>2</mn> <mrow> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> such that for every vertex <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(v \in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(f(v) = \emptyset \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi mathvariant="normal">∅</mi> </mrow> </math></EquationSource> </InlineEquation>, the union of the colors assigned to its neighbors equals [<i>k</i>], and if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(f(v) = \{i\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mi>i</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, then <i>v</i> has a neighbor <i>u</i> with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(i \in f(u)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. The minimum weight of such a function is called the <i>k</i>-rainbow total domination number of <i>G</i> and is denoted by <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\gamma _{k\textrm{rt}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi>k</mi> <mtext>rt</mtext> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We contribute to the study of <i>k</i>-rainbow total domination by proving one conjecture and constructing a counterexample to another. First, we show that the problem of determining whether a graph admits a <i>k</i>-rainbow total dominating function of a given weight is NP-complete. In the second part, we derive an upper bound on the domination number of a graph <i>G</i> in terms of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\gamma _{k\textrm{rt}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi>k</mi> <mtext>rt</mtext> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and the frequency of the least-used color in a <i>k</i>-rainbow total dominating function. This result not only provides an alternative and shorter proof of a known lower bound on <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\gamma _{k\textrm{rt}}(G)/\gamma (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi>k</mi> <mtext>rt</mtext> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">/</mo> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, originally established by Ojakian et al.&#xa0;(2021), but also contributes to disproving their conjecture on the lower bound for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\gamma _{k\textrm{rt}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>γ</mi> <mrow> <mi>k</mi> <mtext>rt</mtext> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(k= 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

On k-Rainbow Total Domination and a Related Conjecture

  • Rija Erveš,
  • Tadeja Kraner Šumenjak,
  • Aleksandra Tepeh

摘要

A k-rainbow total dominating function of a graph G is a function \(f: V(G) \rightarrow 2^{[k]}\) f : V ( G ) 2 [ k ] such that for every vertex \(v \in V(G)\) v V ( G ) with \(f(v) = \emptyset \) f ( v ) = , the union of the colors assigned to its neighbors equals [k], and if \(f(v) = \{i\}\) f ( v ) = { i } , then v has a neighbor u with \(i \in f(u)\) i f ( u ) . The minimum weight of such a function is called the k-rainbow total domination number of G and is denoted by \(\gamma _{k\textrm{rt}}(G)\) γ k rt ( G ) . We contribute to the study of k-rainbow total domination by proving one conjecture and constructing a counterexample to another. First, we show that the problem of determining whether a graph admits a k-rainbow total dominating function of a given weight is NP-complete. In the second part, we derive an upper bound on the domination number of a graph G in terms of \(\gamma _{k\textrm{rt}}(G)\) γ k rt ( G ) and the frequency of the least-used color in a k-rainbow total dominating function. This result not only provides an alternative and shorter proof of a known lower bound on \(\gamma _{k\textrm{rt}}(G)/\gamma (G)\) γ k rt ( G ) / γ ( G ) , originally established by Ojakian et al. (2021), but also contributes to disproving their conjecture on the lower bound for \(\gamma _{k\textrm{rt}}(G)\) γ k rt ( G ) when \(k= 4\) k = 4 .