Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1, 2,..., k} such that for any vertex nu with f(nu) = empty set we have boolean OR(u is an element of NG(nu))f(u) = {1, 2,..., k} The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number gamma(rk)(G) of a graph G, that is the minimum value of Sigma(nu is an element of V(G)) vertical bar f(nu)vertical bar where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that gamma(rk)(T) = vertical bar V(T)vertical bar. (C) 2009 Elsevier B.V. All rights reserved.