Geodesic
Double Roman and double Italian domination
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 721-730

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

Let G be a graph with vertex set V(G). A double Roman dominating function (DRDF) on a graph G is a function f:V(G)⟶{0,1,2,3} that satisfies the following conditions: (i) If f(v)=0, then v must have a neighbor w with f(w)=3 or two neighbors x and y with f(x)=f(y)=2; (ii) If f(v)=1, then v must have a neighbor w with f(w)≥ 2. The weight of a DRDF f is the sum ∑_v∈ V(G)f(v). The double Roman domination number equals the minimum weight of a double Roman dominating function on G. A double Italian dominating function (DIDF) is a function f:V(G)⟶{0,1,2,3} having the property that f(N[u])≥ 3 for every vertex u∈ V(G) with f(u)∈{0,1}, where N[u] is the closed neighborhood of v. The weight of a DIDF f is the sum ∑_v∈ V(G)f(v), and the minimum weight of a DIDF in a graph G is the double Italian domination number. In this paper we first present Nordhaus-Gaddum type bounds on the double Roman domination number which improved corresponding results given in [N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53]. Furthermore, we establish lower bounds on the double Roman and double Italian domination numbers of trees.
Keywords: double Roman domination, double Italian domination 
Volkmann, Lutz. Double Roman and double Italian domination. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 721-730. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a8/
@article{DMGT_2023_43_3_a8,
     author = {Volkmann, Lutz},
     title = {Double {Roman} and double {Italian} domination},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {721--730},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a8/}
}
TY  - JOUR
AU  - Volkmann, Lutz
TI  - Double Roman and double Italian domination
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 721
EP  - 730
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a8/
LA  - en
ID  - DMGT_2023_43_3_a8
ER  - 
%0 Journal Article
%A Volkmann, Lutz
%T Double Roman and double Italian domination
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 721-730
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a8/
%G en
%F DMGT_2023_43_3_a8

[1] H.A. Ahangar, M. Chellali and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017) 1–7. https://doi.org/10.1016/j.dam.2017.06.014

[2] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami and L. Volkmann, An upper bound on the double Roman domination number, J. Comb. Optim. 36 (2018) 81–89. https://doi.org/10.1007/s10878-018-0286-6

[3] F. Azvin and N. Jafari Rad, Bounds on the double Italian domination number of a graph, Discuss. Math. Graph Theory, in press. https://doi.org/10.7151/dmgt.2330

[4] F. Azvin, N. Jafari Rad and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6 (2021) 123–136.

[5] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29. https://doi.org/10.1016/j.dam.2016.03.017

[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Roman domination in graphs, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer 2020) 365–409. https://doi.org/10.1007/978-3-030-51117-3_11

[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination, in: Structures of Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), (Springer 2021).

[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II}, AKCE Int. J. Graphs Comb. 17 (2020) 966–984. https://doi.org/10.1016/j.akcej.2019.12.001

[9] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs (J. Combin. Math. Combin. Comput.), to appear.

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

[11] M. Hajibaba and N. Jafari Rad, A note on the Italian domination number and double Roman domination number in graphs, J. Combin. Math. Combin. Comput. 109 (2019) 169–183.

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

[13] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53. https://doi.org/10.7151/dmgt.2069

[14] R. Khoeilar, H. Karami, M. Chellali and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019) 159–167. https://doi.org/10.1016/j.dam.2019.06.018

[15] D.A. Mojdeh and L. Volkmann, Roman {3}–domination (double Italian domination), Discrete Appl. Math. 283 (2020) 555–564. https://doi.org/10.1016/j.dam.2020.02.001

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

[17] Z. Shao, D.A. Mojdeh and L. Volkmann, Total Roman {3}-domination, Symmetry 12 (2020) 268. https://doi.org/10.3390/sym12020268