Signed double Roman domination in graphs

• Published in: Discrete Applied Mathematics 2019-03, Vol.257, p.1-11
• Main Authors: Ahangar, Hossein Abdollahzadeh, Chellali, Mustapha, Sheikholeslami, Seyed Mahmoud
• Format: Article
• Language: English
• Subjects: Apexes; Double Roman domination; Graphs; Mathematical functions; Minimum weight; Roman domination; Signed double Roman domination; Trees (mathematics)
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2018.09.009

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) ∑u∈N[v]f(u)≥1 holds for any vertex v. The weight of an SDRDF f is ∑u∈V(G)f(u), the minimum weight of an SDRDF is the signed double Roman domination number γ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+249≤γsdR(T)≤n and we characterize all trees attaining each bound.