Extremal Problems for Roman Domination

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γR(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γR(G) + γR(Ḡ) and γR(G)γR(Ḡ), improving known results for domination number. We prove that γR(G) ≤ 8n/11 when ᵟ(G) ≥ 2 and n ≥ 9, and this is sharp