Geodesic
Some Progress on the Double Roman Domination in Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 41-53

Voir la notice de l'article provenant de la source Library of Science

For a graph G = (V,E), a double Roman dominating function (or just DRDF) is a function f : V →0, 1, 2, 3 having the property that if f(v) = 0 for a vertex v, then v has at least two neighbors assigned 2 under f or one neighbor assigned 3 under f, and if f(v) = 1, then vertex v must have at least one neighbor w with f(w) ≥ 2. The weight of a DRDF f is the sum f(V) = Σ_ v ∈ V f(v), and the minimum weight of a DRDF on G is the double Roman domination number of G, denoted by γ_dR (G). In this paper, we derive sharp upper and lower bounds on γ_dR (G) + γ_dR ( G ) and also γ_dR (G ) γ_dR ( G ), where G is the complement of graph G. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.
Keywords: Roman domination, double Roman domination 
@article{DMGT_2019_39_1_a4,
     author = {Rad, Nader Jafari and Rahbani, Hadi},
     title = {Some {Progress} on the {Double} {Roman} {Domination} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {41--53},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a4/}
}
TY  - JOUR
AU  - Rad, Nader Jafari
AU  - Rahbani, Hadi
TI  - Some Progress on the Double Roman Domination in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 41
EP  - 53
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a4/
LA  - en
ID  - DMGT_2019_39_1_a4
ER  - 
%0 Journal Article
%A Rad, Nader Jafari
%A Rahbani, Hadi
%T Some Progress on the Double Roman Domination in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 41-53
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a4/
%G en
%F DMGT_2019_39_1_a4
Rad, Nader Jafari; Rahbani, Hadi. Some Progress on the Double Roman Domination in Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 41-53. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a4/