Bounds on Roman domination numbers of graphs

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 0has a neighbor with label 2. The Roman domination number$\gamma_R(G)$ of $G$ is the minimum of $\Sigma_{vın V(G)} f(v)$ oversuch functions. In this paper, we find lower and upper bounds forRoman domination numbers in terms of the diameter and the girth of~$G$.