Geodesic
A New Upper Bound for the Perfect Italian Domination Number of a Tree
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 1005-1022.

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

A perfect Italian dominating function (PIDF) on a graph G is a function f : V (G) →{ 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 γ_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 ≥ 3, with 𝓁 (T) leaves and s(T) support vertices, γ_I^p (T) ≥4n- 𝓁(T) + 2s (T) - 15, 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 
@article{DMGT_2022_42_3_a19,
     author = {Nazari-Moghaddam, Sakineh and Chellali, Mustapha},
     title = {A {New} {Upper} {Bound} for the {Perfect} {Italian} {Domination} {Number} of a {Tree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1005--1022},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a19/}
}
TY  - JOUR
AU  - Nazari-Moghaddam, Sakineh
AU  - Chellali, Mustapha
TI  - A New Upper Bound for the Perfect Italian Domination Number of a Tree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1005
EP  - 1022
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a19/
LA  - en
ID  - DMGT_2022_42_3_a19
ER  - 
%0 Journal Article
%A Nazari-Moghaddam, Sakineh
%A Chellali, Mustapha
%T A New Upper Bound for the Perfect Italian Domination Number of a Tree
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1005-1022
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a19/
%G en
%F DMGT_2022_42_3_a19
Nazari-Moghaddam, Sakineh; Chellali, Mustapha. A New Upper Bound for the Perfect Italian Domination Number of a Tree. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 1005-1022. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a19/

[1] 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

[2] 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.

[3] 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.1016/j.akcej.2019.12.001

[4] M. Chellai, 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

[5] 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.

[6] 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

[7] 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

[8] 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

[9] 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

[10] 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

[11] M. Livingston and Q.F. Stout, Perfect dominating sets, Congr. Numer. 79 (1990) 187–203.

[12] 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

[13] I. Stewart, Defend the Roman Empire, Sci. Amer. 281 (1999) 136–139. https://doi.org/10.1038/scientificamerican1299-136