Global Roman Domination in Trees

Abstract

A function $f:V(G)\rightarrow \{0,1,2\}$ on graph $G=(V(G),E(G))$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent at least one vertex $v$ for which $f(v)=2$ is a Roman dominating function (RDF). The weight of an RDF is the sum of its function value over all vertices. The Roman domination number of $G$, denoted by $\gamma _{R}(G)$, is the minimum weight of an RDF on $G$. An RDF $f:V(G)\rightarrow \{0,1,2\}$ is called a global Roman dominating function (GRDF) if $f$ is also an RDF of the complement $\overline{G}$ of $G$. The global Roman domination number of $G$, denoted by $\gamma _{gR}(G)$, is the minimum weight of a GRDF on $G$. In this paper, we initiate global Roman domination number and study the basic properties of global Roman domination of a graph. Then we present some sharp bounds for global Roman domination number. In particular, we prove that for any tree of order $n\ge 4$, $\gamma _{gR}(T)\le \gamma _{R}(T)+2$ and we characterize all trees with $\gamma _{gR}(T)=\gamma _{R}(T)+2$ and $\gamma _{gR}(T)= \gamma _{R}(T)+1$.