Total 2-Rainbow Domination in Graphs

A total k-rainbow dominating function on a graph G = (V, E) is a function f : V (G) -> 2({1,2,...,k}) such that (i) boolean OR(u is an element of N(v))f(u) = {1, 2, ... , k} for every vertex v with f(v) = empty set, (ii) boolean OR(u is an element of N(v))f(u) not equal empty set for f(v) not equal empty set. The weight of a total 2-rainbow dominating function is denoted by omega(f) = Sigma(v is an element of V(G)) vertical bar f(V)vertical bar. The total k-rainbow domination number of G is the minimum weight of a total k-rainbow dominating function of G. The minimum total 2-rainbow domination problem (MT2RDP) is to find the total 2-rainbow domination number of the input graph. In this paper, we study the total 2-rainbow domination number of graphs. We prove that the MT2RDP is NP-complete for planar bipartite graphs, chordal bipartite graphs, undirected path graphs and split graphs. Then, a linear-time algorithm is proposed for computing the total k-rainbow domination number of trees. Finally, we study the difference in complexity between MT2RDP and the minimum 2-rainbow domination problem.