On the Roman domination number of a graph

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