Article in volume
Authors:
Lutz Volkmann
Lehrstuhl II für Mathematik, RWTH-Aachen52056 Aachen GERMANY
email: volkm@math2.rwth-aachen.de
Title:
Double Roman and double Italian domination
PDFSource:
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:
- 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 - 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 - 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 - F. Azvin, N. Jafari Rad and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6 (2021) 123–136.
- 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 - 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 - 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).
- 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 - 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.
- 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 - 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.
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
- 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 - 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 - 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 - E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177.
https://doi.org/10.2307/2306658 - Z. Shao, D.A. Mojdeh and L. Volkmann, Total Roman $\{3\}$-domination, Symmetry 12 (2020) 268.
https://doi.org/10.3390/sym12020268
Close