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/