Geodesic
Restrained Roman reinforcement number in graphs
Ural mathematical journal, Tome 8 (2022) no. 2, pp. 81-93
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2022},
     volume = {8},
     number = {2},
     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
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
%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/

[1] Abdollahzadeh Ahangar H., Amjadi J., Chellali M., Nazari-Moghaddam S., Sheikholeslami S. M., “Total Roman reinforcement in graphs.”, Discuss. Math. Graph Theory, 39:4 (2019), 787–803 | DOI

[2] Abdollahzadeh Ahangar H., Mirmehdipour S. R., “Bounds on the restrained Roman domination number of a graph”, Commun. Comb. Optim., 1:1 (2016), 75–82 | DOI

[3] Amjadi J., Asgharsharghi L., Dehgardi N., Furuya M., Sheikholeslami S. M. and Volkmann L., “The $k$-rainbow reinforcement numbers in graphs”, Discrete Appl. Math., 217 (2017), 394–404 | DOI

[4] Amjadi J., Sadeghi H., “Double Roman reinforcement number in graphs”, AKCE Int. J. Graphs Comb., 18:3 (2021), 191–199 | DOI

[5] Ebrahimi N., Amjadi J., Chellali M., Sheikholeslami S.M., “Quasi-total Roman reinforcement in graphs”, AKCE Int. J. Graphs Comb., 2022, 1–8 | DOI

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

[7] Hao G., Sheikholeslami S. M., Wei S., “Italian reinforcement number in graphs”, IEEE Access, 7 (2019), 184448 | DOI

[8] Haynes T. W., Hedetniemi S. T., Slater P. J., Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998, 446 pp. | DOI

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

[10] Kok J., Mynhardt C. M., “Reinforcement in graphs”, Congr. Numer., 79 (1990), 225–231

[11] Pushpam P. R. L., Padmapriea S., “Restrained Roman domination in graphs”, Trans. Comb., 4:1 (2015), 1–17 | DOI

[12] Samadi B., Soltankhah N., Abdollahzadeh Ahangar H., Chellali M., Mojdeh D. A., Sheikholeslami S. M., Valenzuela-Tripodoro J. C., “Restrained condition on double Roman dominating functions”, Appl. Math. Comput., 438 (2023), 127554 | DOI

[13] Shahbazi L., Abdollahzadeh Ahangar H., Khoeilar R., Shekholeslami S. M., “Total $k$-rainbow reinforcement number in graphs”, Discrete Math. Algorithms Appl., 13:1 (2021), 2050101 | DOI

[14] Siahpour F., Abdollahzadeh Ahangar H., Sheikholeslami S. M., “Some progress on the restrained Roman domination”, Bull. Malays. Math. Sci. Soc., 44:7 (2021), 733–751 | DOI

[15] Volkmann L., “Remarks on the restrained Italian domination number in graphs”, Commun. Comb. Optim., 8:1 (2023), 183–191 | DOI

[16] Volkmann L., “Restrained double Italian domination in graphs”, Commun. Comb. Optim., 8:1 (2023), 1–11 | DOI