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/

[1] N. Alon and J. Spencer, The Probabilistic Method (Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, Chichester, 2000).

[2] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466-546. doi: 10.1016/j.dam.2011.12.018

[3] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Dis- crete Appl. Math. 211 (2016) 23-29. doi: 10.1016/j.dam.2016.03.017

[4] S. Bermudo, H. Fernau and J.M. Sigarreta, The differential and the roman domina- tion number of a graph, Appl. Anal. Discrete Math. 8 (2014) 155-171. doi: 10.2298/AADM140210003B

[5] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575-1586. doi: 10.1137/070699688

[6] M. Chellali and N. Jafari Rad, Double equality between the roman domination and independent roman domination numbers in trees, Discuss. Math. Graph Theory 33 (2013) 337-346. doi: 10.7151/dmgt.1669

[7] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22. doi: 10.1016/j.disc.2003.06.004

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).

[9] M.A. Henning and S.T. Hedetniemi, Defending the Roman empire-a new strategy, Discrete Math. 266 (2003) 239-251. doi: 10.1016/S0012-365X(02)00811-7

[10] Ch.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608-619. doi: 10.1007/s10878-012-9482-y

[11] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer.Math.Monthly 63 (1956) 175-177. doi: 10.2307/2306658

[12] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585-594. doi: 10.2307/2589113

[13] I. Stewart, Defend the roman empire!, Sci. Amer. 281 (1999) 136-139. doi: 10.1038/scientificamerican1299-136.