# Global Roman Domination In Trees

M. Atapour, Seyed Mahmoud Sheikholeslami, Lutz Volkmann
Published 2015 · Computer Science, Mathematics
A function $$f:V(G)\rightarrow \{0,1,2\}$$f:V(G)→{0,1,2} on graph $$G=(V(G),E(G))$$G=(V(G),E(G)) satisfying the condition that every vertex $$u$$u for which $$f(u)=0$$f(u)=0 is adjacent at least one vertex $$v$$v for which $$f(v)=2$$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$$G, denoted by $$\gamma _{R}(G)$$γR(G), is the minimum weight of an RDF on $$G$$G. An RDF $$f:V(G)\rightarrow \{0,1,2\}$$f:V(G)→{0,1,2} is called a global Roman dominating function (GRDF) if $$f$$f is also an RDF of the complement $$\overline{G}$$G¯ of $$G$$G. The global Roman domination number of $$G$$G, denoted by $$\gamma _{gR}(G)$$γgR(G), is the minimum weight of a GRDF on $$G$$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$$n≥4, $$\gamma _{gR}(T)\le \gamma _{R}(T)+2$$γgR(T)≤γR(T)+2 and we characterize all trees with $$\gamma _{gR}(T)=\gamma _{R}(T)+2$$γgR(T)=γR(T)+2 and $$\gamma _{gR}(T)= \gamma _{R}(T)+1$$γgR(T)=γR(T)+1.
This paper references

This paper is referenced by