Geodesic
On The Total Roman Domination in Trees
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 519-532.

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

A total Roman dominating function on a graph G is a function f : V (G) → 0, 1, 2 satisfying the following conditions: (i) every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2 and (ii) the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. The weight of a total Roman dominating function f is the value f(V (G)) = Σu∈V(G) f(u). The total Roman domination number γtR(G) is the minimum weight of a total Roman dominating function of G. Ahangar et al. in [H.A. Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517] recently showed that for any graph G without isolated vertices, 2γ(G) ≤ γtR(G) ≤ 3γ(G), where γ(G) is the domination number of G, and they raised the problem of characterizing the graphs G achieving these upper and lower bounds. In this paper, we provide a constructive characterization of these trees.
Keywords: total Roman dominating function, total Roman domination number, trees 
@article{DMGT_2019_39_2_a14,
     author = {Amjadi, Jafar and Sheikholeslami, Seyed Mahmoud and Soroudi, Marzieh},
     title = {On {The} {Total} {Roman} {Domination} in {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {519--532},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a14/}
}
TY  - JOUR
AU  - Amjadi, Jafar
AU  - Sheikholeslami, Seyed Mahmoud
AU  - Soroudi, Marzieh
TI  - On The Total Roman Domination in Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 519
EP  - 532
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a14/
LA  - en
ID  - DMGT_2019_39_2_a14
ER  - 
%0 Journal Article
%A Amjadi, Jafar
%A Sheikholeslami, Seyed Mahmoud
%A Soroudi, Marzieh
%T On The Total Roman Domination in Trees
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 519-532
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a14/
%G en
%F DMGT_2019_39_2_a14
Amjadi, Jafar; Sheikholeslami, Seyed Mahmoud; Soroudi, Marzieh. On The Total Roman Domination in Trees. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 519-532. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a14/

[1] H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami and M. Soroudi, Bounds on the total Roman domination numbers, Ars Combin., to appear.

[2] H. Abdollahzadeh Ahangar, A. Bahremandpour, S.M. Sheikholeslami, N.D. Soner, Z. Tahmasbzadehbaee and L. Volkmann, Maximal Roman domination numbers in graphs, Util. Math. 103 (2017) 245–258.

[3] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517. doi:10.2298/AADM160802017A

[4] H. Abdollahzadeh Ahangar, T.W. Haynes and J.C. Valenzuela-Tripodoro, Mixed Roman domination in graphs, Bull. Malays. Math. Sci. Soc. 40 (2017) 1443–1454. doi:10.1007/s40840-015-0141-1

[5] J. Amjadi, S. Nazari-Moghaddam and S.M. Sheikholeslami, Global total Roman domination in graphs, Discrete Math. Algorithms Appl. 09 (2017) ID: 1750050. doi:10.1142/S1793830917500501

[6] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Australas. J. Combin. 69 (2017) 271–285.

[7] J. Amjadi, S.M. Sheikholeslami and M. Soroudi, Nordhaus-Gaddum bounds for total Roman domination, J. Comb. Optim. 35 (2018) 126–133. doi:10.1007/s10878-017-0158-5

[8] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29. doi:10.1016/j.dam.2016.03.017

[9] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman {2} -domination, Discrete Appl. Math. 204 (2016) 22–28. doi:10.1016/j.dam.2015.11.013

[10] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. doi:10.1016/j.disc.2003.06.004

[11] M.R. Garey and D.S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness (W.H. Freeman and Co., San Francisco, Calif., 1979).

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).

[13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).

[14] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003) 239–251. doi:10.1016/S0012-365X(02)00811-7

[15] L.L. Kelleher and M.B. Cozzens, Dominating sets in social network graphs, Math. Social Sci. 16 (1988) 267–279. doi:10.1016/0165-4896(88)90041-8

[16] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608–619. doi:10.1007/s10878-012-9482-y

[17] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594. doi:10.1080/00029890.2000.12005243

[18] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136–138. doi:10.1038/scientificamerican1299-136