On the double Roman domination in graphs

• Published in: Discrete Applied Mathematics 2017-12, Vol.232, p.1-7
• Main Authors: Abdollahzadeh Ahangar, Hossein, Chellali, Mustapha, Sheikholeslami, Seyed Mahmoud
• Format: Article
• Language: English
• Subjects: Combinatorics; Double Roman domination; Graphs; Mathematical functions; Mathematics; Minimum weight; Roman [formula omitted]-domination; Roman domination
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2017.06.014

A double Roman dominating function (DRDF) on a graph G=(V,E) is a function f: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))=∑u∈V(G)f(u). The double Roman domination number γdR(G) is the minimum weight of a DRDF on G. First we show that the decision problem associated with γ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 γdR(G) is provided.