Outer independent Roman dominating functions in graphs
Hossein Abdollahzadeh Ahangar, Mustapha Chellali, Vladimir Samodivkin · International Journal of Computer Mathematics · 2017
A Roman dominating function (RDF) on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and V0 is an independent set. The outer-independent Roman domination number γoiR(G) is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number γoiR(G) is NP-complete for bipartite graphs. Then we present lower and upper bounds on γoiR(G). Moreover, we characterize graphs with small or large outer-independent Roman domination number.