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 label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of v∈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(G) and γR(G)γR(G), improving known results for domination number. We prove that γR(G) ≤ 8n/11 when δ(G) ≥ 2 and n ≥ 9, and this is sharp. We conjecture that γR(G) ≤ ⌈2n/3 ⌉ when G is 2-connected, which we prove for a special class.