# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

# Discussiones Mathematicae Graph Theory

Article in volume

Authors:

L. Volkmann

Lutz Volkmann

Lehrstuhl II für Mathematik, RWTH-Aachen52056 Aachen GERMANY

email: volkm@math2.rwth-aachen.de

Title:

Double Roman and double Italian domination

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 721-730

Received: 2020-10-21 , Revised: 2021-02-10 , Accepted: 2021-02-15 , Available online: 2021-03-11 , https://doi.org/10.7151/dmgt.2399

Abstract:

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)\longrightarrow\{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)\ge 2$. The weight of a DRDF $f$ is the sum $\sum_{v\in 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)\longrightarrow \{0,1,2,3\}$ having the property that $f(N[u])\geq 3$ for every vertex $u\in V(G)$ with $f(u)\in \{0,1\}$, where $N[u]$ is the closed neighborhood of $v$. The weight of a DIDF $f$ is the sum $\sum_{v\in 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

References:

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