On the double Roman domination in graphs

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 w...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2017.06.014