Geodesic
Total Roman Reinforcement in Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 787-803.

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

A total Roman dominating function on a graph G is a labeling f : V (G) → 0, 1, 2 such that every vertex with label 0 has a neighbor with label 2 and the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. The minimum weight of a total Roman dominating function on a graph G is called the total Roman domination number of G. The total Roman reinforcement number rtR(G) of a graph G is the minimum number of edges that must be added to G in order to decrease the total Roman domination number. In this paper, we investigate the proper- ties of total Roman reinforcement number in graphs, and we present some sharp bounds for rtR(G). Moreover, we show that the decision problem for total Roman reinforcement is NP-hard for bipartite graphs.
Keywords: total Roman domination number, total Roman reinforcement number 
@article{DMGT_2019_39_4_a1,
     author = {Ahangar, H. Abdollahzadeh and Amjadi, J. and Chellali, M. and Nazari-Moghaddam, S. and Sheikholeslami, S.M.},
     title = {Total {Roman} {Reinforcement} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {787--803},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a1/}
}
TY  - JOUR
AU  - Ahangar, H. Abdollahzadeh
AU  - Amjadi, J.
AU  - Chellali, M.
AU  - Nazari-Moghaddam, S.
AU  - Sheikholeslami, S.M.
TI  - Total Roman Reinforcement in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 787
EP  - 803
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a1/
LA  - en
ID  - DMGT_2019_39_4_a1
ER  - 
%0 Journal Article
%A Ahangar, H. Abdollahzadeh
%A Amjadi, J.
%A Chellali, M.
%A Nazari-Moghaddam, S.
%A Sheikholeslami, S.M.
%T Total Roman Reinforcement in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 787-803
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a1/
%G en
%F DMGT_2019_39_4_a1
Ahangar, H. Abdollahzadeh; Amjadi, J.; Chellali, M.; Nazari-Moghaddam, S.; Sheikholeslami, S.M. Total Roman Reinforcement in Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 787-803. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a1/

[1] H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami and M. Soroudi, On the total Roman domination number of graphs, Ars Combin., to appear.

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

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

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

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

[6] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219. doi:10.1002/net.3230100304

[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. doi:10.1016/j.disc.2003.06.004

[8] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009) 3447–3451. doi:10.1016/j.disc.2008.09.043

[9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman, San Francisco, 1979).

[10] M.A. Henning, A survey on selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32–63. doi:10.1016/j.disc.2007.12.044

[11] M.A. Henning, N. Jafari Rad and J. Raczek, A note on total reinforcement in graphs, Discrete Appl. Math. 159 (2011), 1443–1446. doi:10.1016/j.dam.2011.04.024

[12] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013). doi:10.1007/978-1-4614-6525-6

[13] N. Jafari Rad and S. Sheikholeslami, Roman reinforcement in graphs, Bull. Inst. Combin. Appl. 61 (2011) 81–90.

[14] C.-H. Liu and G.J. Chang, Roman domination on 2 -connected graphs, SIAM J. Discrete Math. 26 (2012) 193–205. doi:10.1137/080733085

[15] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012) 1386–1391. doi:10.1016/j.disc.2011.12.021

[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] P. Pavlič and J. Žerovnik, Roman domination number of the Cartesian products of paths and cycles, Electron. J. Combin. 19 (3) (2012) #P19.

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

[19] N. Sridharan, M.D. Elias and V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2007) 197–202.

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

[21] I.G. Yero and J.A. Rodríguez-Velázquez, Roman domination in Cartesian product graphs and strong product graphs, Appl. Anal. Discrete Math. 7 (2013) 262–274. doi:10.2298/AADM130813017G