Article in volume
Authors:
Mustapha Chellali
Department of MathematicsUniversity of BlidaB.P. 270, Blida, ALGERIA
email: m_chellali@yahoo.com
Title:
A new upper bound for the perfect Italian domination number of a tree
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 1005-1022
Received: 2019-09-03 , Revised: 2020-04-08 , Accepted: 2020-04-10 , Available online: 2020-05-11 , https://doi.org/10.7151/dmgt.2324
Abstract:
A perfect Italian dominating function (PIDF) on a graph $G$ is a function
$f:V(G)\rightarrow\{0,1,2\}$ satisfying the condition that for every vertex
$u$ with $f(u)=0$, the total weight of $f$ assigned to the neighbors of $u$ is
exactly two. The weight of a PIDF is the sum of its functions
values over all vertices. The perfect Italian domination number of $G$,
denoted $\gamma_{I}^{p}(G)$, is the minimum weight of a PIDF of $G$. In this
paper, we show that for every tree $T$ of order $n\geq3$, with $\ell(T)$
leaves and $s(T)$ support vertices, $\gamma_{I}^{p}(T)\leq\frac{4n-\ell
(T)+2s(T)-1}{5}$, improving a previous bound given by T.W. Haynes and M.A.
Henning in [Perfect Italian domination in trees, Discrete Appl. Math. 260
(2019) 164–177].
Keywords:
Italian domination, Roman domination, perfect Italian domination
References:
- 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, 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.
- 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)) 273–307.
https://doi.org/10.1007/978-3-030-58892-2_10 - M. Chellai, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, Varieties of Roman dominationm II, AKCE Int. J. Graphs Comb. 17 (2020) 966–984.
https://doi.org/10.1016/j.akcej.2019.12.001 - M. Chellai, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020) 141–171.
- M. Chellai, N. Jafari Rad, S.M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: A survey, Discuss. Math. Graph Theory, in press.
https://doi.org/10.7151/dmgt.2313 - E.J. Cockayne, P.A. Dreyer Jr., 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. Darkooti, A. Alhevaz, S. Rahimi and H. Rahbani, On perfect Roman domination number in trees: complexity and bounds, J. Comb. Optim. 38 (2019) 712–720.
https://doi.org/10.1007/s10878-019-00408-y - T.W. Haynes and M.A. Henning, Perfect Italian domination in trees, Discrete Appl. Math. 260 (2019) 164–177.
https://doi.org/10.1016/j.dam.2019.01.038 - M.A. Henning, W.F. Klostermeyer and G. MacGillivray, Perfect Roman domination in trees, Discrete Appl. Math. 236 (2018) 235–245.
https://doi.org/10.1016/j.dam.2017.10.027 - M. Livingston and Q.F. Stout, Perfect dominating sets, Congr. Numer. 79 (1990) 187–203.
- 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