Upper bounds on Roman domination numbers of graphs

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