Geodesic
Restrained Roman reinforcement number in graphs
Ural mathematical journal, Tome 8 (2022) no. 2, pp. 81-93

Voir la notice de l'article provenant de la source Math-Net.Ru

A restrained Roman dominating function (RRD-function) on a graph $G=(V,E)$ is a function $f$ from $V$ into $\{0,1,2\}$ satisfying: (i) every vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)=2$; (ii) the subgraph induced by the vertices assigned 0 under $f$ has no isolated vertices. The weight of an RRD-function is the sum of its function value over the whole set of vertices, and the restrained Roman domination number is the minimum weight of an RRD-function on $G.$ In this paper, we begin the study of the restrained Roman reinforcement number $r_{rR}(G)$ of a graph $G$ defined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Roman domination number. We first show that the decision problem associated with the restrained Roman reinforcement problem is NP-hard. Then several properties as well as some sharp bounds of the restrained Roman reinforcement number are presented. In particular it is established that $r_{rR}(T)=1$ for every tree $T$ of order at least three.
Keywords: restrained Roman domination, restrained Roman reinforcement. 
@article{UMJ_2022_8_2_a6,
     author = {Saeed Kosari and Seyed Mahmoud Sheikholeslami and Mustapha Chellali and Maryam Hajjari},
     title = {Restrained {Roman} reinforcement number in graphs},
     journal = {Ural mathematical journal},
     pages = {81--93},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2022_8_2_a6/}
}
TY  - JOUR
AU  - Saeed Kosari
AU  - Seyed Mahmoud Sheikholeslami
AU  - Mustapha Chellali
AU  - Maryam Hajjari
TI  - Restrained Roman reinforcement number in graphs
JO  - Ural mathematical journal
PY  - 2022
SP  - 81
EP  - 93
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UMJ_2022_8_2_a6/
LA  - en
ID  - UMJ_2022_8_2_a6
ER  - 
%0 Journal Article
%A Saeed Kosari
%A Seyed Mahmoud Sheikholeslami
%A Mustapha Chellali
%A Maryam Hajjari
%T Restrained Roman reinforcement number in graphs
%J Ural mathematical journal
%D 2022
%P 81-93
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UMJ_2022_8_2_a6/
%G en
%F UMJ_2022_8_2_a6
Saeed Kosari; Seyed Mahmoud Sheikholeslami; Mustapha Chellali; Maryam Hajjari. Restrained Roman reinforcement number in graphs. Ural mathematical journal, Tome 8 (2022) no. 2, pp. 81-93. http://geodesic.mathdoc.fr/item/UMJ_2022_8_2_a6/