Article in volume
Authors:
Title:
Bounds on the double Italian domination number of a graph
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1129-1137
Received: 2020-01-30 , Revised: 2020-05-07 , Accepted: 2020-05-11 , Available online: 2020-05-25 , https://doi.org/10.7151/dmgt.2330
Abstract:
For a graph $G$, a Roman $\{3\}$-dominating function is a
function $f:V\longrightarrow \{0,1,2,3\}$ having the property
that for every vertex $u\in V$, if $f(u)\in \{0,1\}$, then
$f(N[u])\geq 3$. The weight of a Roman $\{3\}$-dominating
function is the sum $w(f)= f(V ) = \sum_{v\in V}f(v)$, and the
minimum weight of a Roman $\{3\}$-dominating function is the
Roman $\{3\}$-domination number, denoted by
$\gamma_{\{R3\}}(G)$. In this paper, we present a sharp lower
bound for the double Italian domination number of a graph, and
improve previous bounds given in [D.A. Mojdeh and L. Volkmann, Roman
$\{3\}$-domination $($double Italian domination), Discrete Appl. Math. (2020),
in press]. We also present a probabilistic upper bound for a generalized version
of double Italian domination number of a graph, and show that the given bound
is asymptotically best possible.
Keywords:
Italian domination, double Italian domination, probabilistic methods
References:
- 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, T.W. Haynes, S.T. Hedetniemi and A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016) 22–28.
https://doi.org/10.1016/j.dam.2015.11.013 - M. Chellali, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Combin. 17 (2020) 966–984.
- 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 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).
- M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557–564.
https://doi.org/10.1016/j.dam.2016.09.035 - W. Klostermeyer and G. MacGillivray, Roman, Italian, and $2$-domination (J. Combin. Math. Combin. Comput.), to appear.
- 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 - Z. Shao, D.A. Mojdeh and L. Volkmann, Total Roman $\{3\}$-domination in graphs, Symmetry 12 (2020) 1–15.
https://doi.org/10.3390/sym12020268 - C.S. ReVelle and K.E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594.
https://doi.org/10.1080/00029890.2000.12005243 - I. Stewart, Defend the Roman Empire !, Sci. Amer 281 (1999) 136–139.
https://doi.org/10.1038/scientificamerican1299-136
Close