Total \(k\)-rainbow domination subdivision number in graphs (Q2209470)

A \(k\)-rainbow dominating function \(f\) on \(G\), is called a total \(k\)-rainbow dominating function (T\(k\)RDF) if the subgraph of \(G\) induced by the set \(\{v \in V (G) \mid f(v) \ne \emptyset\}\) has no isolated vertex. The total \(k\)-rainbow domination number of \(G\), \(\gamma_{trk}(G)\), is the minimum weight of a T\(k\)RDF of \(G\). The total \(k\)-rainbow domination subdivision number \(\operatorname{sd}_{\gamma_{trk}} (G)\) of a graph \(G\) is the minimum number of edges that must be subdivided (where each edge in \(G\) can be subdivided at most once) in order to increase the total \(k\)-rainbow domination number of \(G\). Let \(X = \{1, 2,\dots, 3(k - 1)\}\), and let \(\mathcal{Y}\) be the set that consists of all \(k\)-subsets of \(X\). Clearly, \(|\mathcal{Y}|=\binom{3(k-1)}{k}\). Let \(\mathcal{G}\) be the graph with vertex set \(X \cup \mathcal{Y}\) and with edge set constructed as follows: add an edge joining every two distinct vertices of \(X\) and for each \(x \in X\) and \(Y \in \mathcal{Y}\), add an edge joining \(x\) and \(Y\) if and only if \(x \in Y\). Then, \(\mathcal{G}\) is a connected graph of order \(n=\binom{3(k-1)}{k}+ 3(k -1)\). The main results of the paper are as follows: \begin{itemize} \item[1.] Let \(G\) be a graph and \(u \in V (G)\) be a vertex with degree at least two. Then \(\operatorname{sd}_{\gamma_{trk}} (G) \le \deg(u)\). \item[2.] For any connected graph \(G\) of order \(n \ge 3\) with \(\delta(G) = 1\), \[ \operatorname{sd}_{\gamma_{tr2}} (G) \le \min\{\gamma_{tr2}(G)-1, \alpha^\prime(G)+1\}, \] where \(\alpha^\prime(G)\) is the matching number of \(G\). This bound is sharp for complete graphs. \item[3.] For any integer \(k \ge 4\), \(\operatorname{sd}_{\gamma_{tr2}} (\mathcal{G}) = k\). \end{itemize}