Isolate Roman domination in graphs.

Let G be a graph with the vertex set V. A function f : V → { 0 , 1 , 2 } is called a Roman dominating function of G , if every vertex v with f (v) = 0 is adjacent to at least one vertex u with f (u) = 2. The weight of a Roman dominating function f is equal to ∑ v ∈ V (G) f (v). The minimum weight of a Roman dominating function of G is called the Roman domination number of G , denoted by γ R (G). In this paper, we initiate the study of a variant of Roman dominating functions. A function f : V (G) → { 0 , 1 , 2 } is called an isolate Roman dominating function of G , if f is a Roman dominating function and there is a vertex v with f (v) = 0 which is not adjacent to any vertex u with f (u) = 0. The minimum weight of an isolate Roman dominating function of G is called the isolate Roman domination number of G , denoted by γ I R (G). We present some upper bound on the isolate Roman domination number of a graph G in terms of its Roman domination number and its domination number. Moreover, we present some classes of graphs G with γ I R (G) = γ R (G). Finally, we show that the decision problem associated with the isolate Roman dominating functions is NP-complete for bipartite graphs and chordal graphs. [ABSTRACT FROM AUTHOR]