Bounding the k-rainbow total domination number

NEW

Problem: For finite simple undirected graphs and integer $k\ge 2$, let $\gamma_{rk}(G)$ be the minimum weight of a $k$-rainbow dominating function and $\gamma_{krt}(G)$ the minimum weight of a $k$-rainbow total dominating function. Interpreting “tight bound” as the least constant

the question asks for $a(k)$.

Result: The sharp answer is

Upper bound: if $f$ is a minimum $k$-rainbow dominating function, add one arbitrary extra color to every singleton label. The resulting function has no singleton labels, remains rainbow dominating, and has weight at most $2\|f\|$. Hence

Sharpness is not only due to isolated vertices, though $K_1$ already gives equality: $\gamma_{rk}(K_1)=1$ and $\gamma_{krt}(K_1)=2$.

Even among connected graphs without isolated vertices, no constant $<2$ works. Fix $q\ge2$. Construct $G_{k,q}$ with vertices $x_{i,t}$ for $i\in[k]$, $0\le t<q$, plus vertices $y_0$ and $y_{i,t}$ for $i\in[k]$, $1\le t<q$. Join $y_0$ to all $x_{i,0}$, and join $y_{i,t}$ to $x_{i,t}$ and to all $x_{j,0}$ with $j\ne i$. This graph is connected and has no isolated vertices.

Define $f(x_{i,t})=\{i\}$ and $f(y)=\emptyset$. Every empty $y$-vertex sees all $k$ colors, so $f$ is a $k$-RDF of weight $kq$. Thus $\gamma_{rk}(G_{k,q})\le kq$.

For any $k$-RTDF $g$, each leaf $x_{i,t}$, $t\ge1$, has unique neighbor $y_{i,t}$. If $g(x_{i,t})=\emptyset$, then $g(y_{i,t})=[k]$, weight at least $k\ge2$. If $g(x_{i,t})$ is singleton, then $y_{i,t}$ must contain that color. If $|g(x_{i,t})|\ge2$, the pair already has weight at least $2$. Hence

for all $i,t\ge1$. Summing over the disjoint pairs gives

Therefore

which tends to $2$. Thus no $a(k)<2$ is possible.

So the paper’s suggested expectation $a(k)<2$ for $k\ge3$ is not correct as a uniform sharp bound; pointwise strictness does not imply a uniform gap.

Citation: The upper bound $\gamma_{krt}(G)\le2\gamma_{rk}(G)$ is Proposition in Ojakian, Škrekovski, and Tepeh, “Bounding the $k$-rainbow total domination number,” arXiv:2003.09470. The sharpness construction above supplies the missing resolution.