Note on 2-rainbow domination and Roman domination in graphs

A Roman dominating function of a graph G is a function f : V -> (0, 1, 2) such that every vertex with 0 has a neighbor with 2. The minimum off (V (G)) = Sigma(v is an element of V) f(v) over all such functions is called the Roman domination number gamma(R)(G). A 2-rainbow dominating function of a graph G is a function g that assigns to each vertex a set of colors chosen from the set (1, 2), for each vertex v is an element of V (G) such that g(v) = phi, we have boolean OR(u is an element of N(v))g(u) = {1, 2}.The 2-rainbow domination number gamma(r2)(G) is the minimum of w(g) = Sigma(v is an element of v) |g(v)| over all such functions. We prove gamma(r2)(G) <= gamma(R)(G) and obtain sharp lower and upper bounds for gamma(r2)(G) + gamma(r2)((G) over bar). We also show that for any connected graph G of order n >= 3. gamma(r2) (G) + < n. Finally, we give a proof of the characterization of graphs with gamma(R)(G) = gamma(G) + k for 2 <= k <= gamma(G). (C) 2010 Elsevier Ltd. All rights reserved.