Signed double Roman domination in graphs

A signed double Roman dominating function (SDRDF) on a graph G = (V, E) is a function f : V(G) -> {-1, 1, 2, 3} such that (i) every vertex v with f(v) = -1 is adjacent to at least two vertices assigned a 2 or to at least one vertex w with f(w) = 3, (ii) every vertex v with f(v) = 1 is adjacent to at least one vertex w with f (w) >= 2 and (iii) Sigma(u is an element of n [v]) f(u) >= 1 holds for any vertex v. The weight of an SDRDF f is Sigma(u is an element of v) (G) f(u), the minimum weight of an SDRDF is the signed double Roman domination number gamma(sdR)(G) of G. In this paper, we prove that the signed double Roman domination problem is NP-complete for bipartite and chordal graphs. We also prove that for any tree T of order n >= 2. -5n+24/9 <= gamma(sdR)(T) <= n and we characterize all trees attaining each bound. (C) 2018 Elsevier B.V. All rights reserved.