Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer kk, a kk-rainbow dominating function of a graph GG is a function ff from V(G)V(G) to the set of all subsets of {1,2,…,k}{1,2,…,k} such that for any vertex vv with f(v)=0̸f(v)=0̸ we have ∪u∈NG(v)f(u)={1,2,…,k}∪u∈NG(v)f(u)={1,2,…,k}. The 11-rainbow domination is the same as the ordinary domination. The kk-rainbow domination problem is to determine the kk-rainbow domination number γrk(G) of a graph GG, that is the minimum value of ∑v∈V(G)|f(v)|∑v∈V(G)|f(v)| where ff runs over all kk-rainbow dominating functions of GG. In this paper, we prove that the kk-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the kk-rainbow domination problem on trees. For a given tree TT, we also determine the smallest kk such that γrk(T)=|V(T)|.