On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f : V(G) -> {0, 1, 2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number gamma(R)(G) of G is the minimum of Sigma(v is an element of V(G)) f(v) over such functions. A Roman dominating function of G of weight gamma(R)(G) is called a gamma(R)(G)-function. A Roman dominating function f : V -> {0, 1, 2} can be represented by the ordered partition (V-0, V-1, V-2) of V, where V-i = {v is an element of V vertical bar f(v) = i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of vertical bar V-0 vertical bar, vertical bar V-1 vertical bar, vertical bar V-2 vertical bar for a gamma(R)-function f = (V-0, V-1, V-2) of a graph G? In this paper we first show that for any connected graph G of order n >= 3, gamma(R)(G) + gamma(G)/2 <= n, where gamma(G) is the domination number of G. Also we prove that for any gamma(R)-function f = (V-0, V-1, V-2) of a connected graph G of order n >= 3, vertical bar V-0 vertical bar >= n/5 + 1, vertical bar V-1 vertical bar <= 4n/5 - 2 and vertical bar V-2 vertical bar <= 2n/5. (C) 2008 Elsevier B.V. All rights reserved.