On the double Roman domination in graphs

A double Roman dominating function (DRDF) on a graph G = (V, E) is a functionf : V(G) -> (0, 1, 2, 3} having the property that if f(v) = 0, then vertex v has at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with f(w) >= 2. The weight of a DRDF is the value f (V(G)) Sigma(u is an element of V(G))f(u). The double Roman domination number gamma(dR)(G) is the minimum weight of a DRDF on G. First we show that the decision problem associated with gamma(dR)(G) is NP-complete for bipartite and chordal graphs. Then we present some sharp bounds on the double Roman domination number which partially answer an open question posed by Beeler et al. (2016) in their introductory paper on double Roman domination. Moreover, a characterization of graphs G with small gamma(dR)(G) is provided. (C) 2017 Elsevier B.V. All rights reserved.