Complexity of 2-rainbow total domination problem (Q6607381)

A \(k\)-rainbow dominating function \(f\) on \(G\), is called a \(k\)-rainbow total dominating function (\(kRTDF\)) of the graph \(G\) if for every \(v \in V (G)\) such that \(f (v) = \{i\}\) for some \(i \in [k]\), there exists some \(u \in N(v)\) such that \(i \in f (u)\). The minimum weight of a \(kRTDF\) is called the \(k\)-rainbow total domination number of \(G\), \(\gamma_{krt}(G)\). Let \(G \circ_{v} H\) be the rooted product of graphs \(G\) and \(H\) which are defined as the graph obtained from \(G\) and \(H\) by taking one copy of \(G\) and \(n_G\) copies of \(H\), and for every \(i \in [n_G]\) identifying \(g_i \in V (G)\) with the root vertex \(v\) in \(H_i\), the \(i\)-th copy of \(H\). For an arbitrary graph \(H\), the graph \(H^+\) denotes a graph obtained from \(H\) by attaching a pendant vertex \(v\) to its support vertex \(x \in V (H)\).\N\NThe main results of the paper are as follows:\N\N1. Let \(k\) and \(n\) be positive integers such that \(n > k > 1\). For a connected graph \(G\) of order \(n\) we have \(\gamma_{krt}(G) = k\) if and only if \(G\) contains a spanning subgraph isomorphic to a complete bipartite graph \(K_{s,n-s}\) where \(s \le \lfloor \frac{k}{2} \rfloor.\)\N\N2. Let \(2 \le k < n_Gn_H\) and let \(G\) and \(H\) be arbitrary nontrivial graphs of order \(n_G\) and \(n_H\). Then,\N\[\Nn_G\gamma_{krt}(H) \ge \gamma_{krt}(G \circ_{v} H) \ge \begin{cases} n_Gk; & k< n_H; \\\Nk + (n_G-1)(n_H-1); & n_H \le k < n_H + n_G-1\\\Nn_Gn_H & k \ge n_H + n_G-1. \end{cases}\N\]\N3. Let \(G\) and \(H\) be arbitrary nontrivial graphs. Then \(\gamma_{krt}(G \circ_{v} H^+) \ge n_G\gamma_{krt}(H)\), and the bound is tight.\N\N4. The \(2\)-rainbow total dominating function is NP-complete.