General Bounds on Rainbow Domination Numbers

A k-rainbow dominating function of a graph G is a function f from the vertices V(G) to 2{1,2,…,k} such that, for all v∈V(G), either f(v)≠∅ or ⋃u∈N[v]f(u)={1,2,…,k}. The k-rainbow domination number of a graph G is then defined to be the minimum weight w(f)=∑v∈V(G)|f(v)| of a k-rainbow dominating function. In this work, we prove sharp upper bounds on the k-rainbow domination number for all values of k. Furthermore, we also consider the problem with minimum degree restrictions on the graph