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) ∪ u ∈ N (v) f (u) = { 1 , 2 , ... , k } for every vertex v with f (v) = ∅ , (ii) ∪ u ∈ N (v) f (u) ≠ ∅ for f (v) ≠ ∅ . The weight of a total 2-rainbow dominating function is denoted by ω (f) = ∑ v ∈ V (G) | f (v) | . 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. [ABSTRACT FROM AUTHOR]