Upper bounds on Roman domination numbers of graphs

A Roman dominating function   of a graph GG is a function f:V(G)→{0,1,2}f:V(G)→{0,1,2} such that whenever f(v)=0f(v)=0 there exists a vertex uu adjacent to vv with f(u)=2f(u)=2. The weight   of ff is w(f)=∑v∈V(G)f(v)w(f)=∑v∈V(G)f(v). The Roman domination number  γR(G)γR(G) of GG is the minimum weight of a Roman dominating function of GG. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 33. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given.