On the Roman domination number of a graph

AbstractA 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 γR(G) of G is the minimum of ∑v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γR(G) is called a γR(G)-function. A Roman dominating function f:V⟶{0,1,2} can be represented by the ordered partition (V0,V1,V2) of V, where Vi={v∈V∣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 |V0|,|V1|,|V2| for a γR-function f=(V0,V1,V2) of a graph G? In this paper we first show that for any connected graph G of order n≥3, γR(G)+γ(G)2≤n, where γ(G) is the domination number of G. Also we prove that for any γR-function f=(V0,V1,V2) of a connected graph G of order n≥3, |V0|≥n5+1, |V1|≤4n5−2 and |V2|≤2n5