On the Outer-Independent Roman Domination in Graphs

Abstract

[EN] Let G be a graph with no isolated vertex and f:V(G)->{0,1,2} a function. Let V-i={v is an element of V(G):f(v)=i} for every i is an element of{0,1,2}. The function f is an outer-independent Roman dominating function on G if V0 is an independent set and every vertex in V-0 is adjacent to at least one vertex in V-2. The minimum weight omega(f)= Sigma v is an element of V(G)f(v) among all outer-independent Roman dominating functions f on G is the outer-independent Roman domination number of G. This paper is devoted to the study of the outer-independent Roman domination number of a graph, and it is a contribution to the special issue "Theoretical Computer Science and Discrete Mathematics" of Symmetry. In particular, we obtain new tight bounds for this parameter, and some of them improve some well-known results. We also provide closed formulas for the outer-independent Roman domination number of rooted product graphs.