Weak Roman Domination In Graphs

Motivated by an article by lan Stewart [11] (Defend the Roman empire!, Scientific American, Dec. 1999, pp. 136-138), M. A. Henning and S. T. Hedetniemi [1] explore a new strategy of defending the Roman Empire that has the potential of saving the Emperor Constantine the Great substantial costs of maintaining legions, while still defending the Roman Empire. In graph theoretic terminology, let G=(V,E) be a graph and let f be function f∶V(?){0, 1, 2}. A vertex u with f(u)=0 is said to be undefended with respect to f if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u)=0 is adjacent to a vertex v with f(v)＞0 such that the function f′: V(?){0, 1, 2}, defined by f′(u)=1, f′(v)=f(v)-1 and f′(w)=f(w) if w∈V-{u, v}, has no undefended vertex. The weight of f is w(f) =Σ_v∈V f(v). The weak Roman domination number, denotedγ_Υ(G), is the minimum weight of a WRDF in G. In this paper, I study the graph theoretic properties of this variant of the domination number of a graph, and I characterize trees T for whichγ_Υ(T)=γ(T) and graphs G for whichγ_Υ(G)=γ(G)+1, and I give the graph G some properties withγ_Υ(G)=2γ(G).