Bounds on Roman domination numbers of graphs


B.P. Mobaraky, S.M. Sheikholeslami


Roman dominating function of a graph $G$ is a labeling function $f\:V(G)\rightarrow \{0, 1, 2\}$ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number $\gamma_R(G)$ of $G$ is the minimum of $\Sigma_{v\in V(G)} f(v)$ over such functions. In this paper, we find lower and upper bounds for Roman domination numbers in terms of the diameter and the girth of~$G$.