On k-Rainbow Total Domination and a Related Conjecture

Abstract A k -rainbow total dominating function of a graph G is a function $$f: V(G) \rightarrow 2^{[k]}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>→</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> such that for every vertex $$v \in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> with $$f(v) = \emptyset $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>∅</mml:mi> </mml:mrow> </mml:math> , the union of the colors assigned to its neighbors equals [ k ], and if $$f(v) = \{i\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mi>i</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> , then v has a neighbor u with $$i \in f(u)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mtext>rt</mml:mtext> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mtext>rt</mml:mtext> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mtext>rt</mml:mtext> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>γ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , originally established by Ojakian et al. (2021), but also contributes to disproving their conjecture on the lower bound for $$\gamma _{k\textrm{rt}}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>γ</mml:mi> <mml:mrow> <mml:mi>k</mml:mi> <mml:mtext>rt</mml:mtext>