Abstract

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$.

Keywords: Roman domination number, diameter, girth.

MSC: 05C69, 05C05

Pages:  247--253     

Volume  60 ,  Issue  4 ,  2008