Some progress on the double Roman domination in graphs
Nader Jafari Rad, Hadi Rahbani · Discussiones Mathematicae Graph Theory · 2018
For a graph G = (V, E), a double Roman dominating function (or just DRDF) is a function f : V - {0, 1, 2, 3} having the property that if f (v) = 0 for a vertex v, then v has at least two neighbors assigned 2 under f or one neighbor assigned 3 under f , and if f (v) = 1, then vertex v must have at least one neighbor w with f (w) 2. The weight of a DRDF f is the sum f (V ) = vV f (v), and the minimum weight of a DRDF on G is the double Roman domination number of G, denoted by dR (G). In this paper, we derive sharp upper and lower bounds on dR (G) + dR (G) and also dR (G) dR (G), where G is the complement of graph G. We also show that the decision problem for the double Roman domination number is NPcomplete even when restricted to bipartite graphs and chordal graphs.