RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS

Saeed Kosari     (Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, Taiwan, Province of China)
Seyed Mahmoud Sheikholeslami     (Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R., Iran, Islamic Republic of)
Mustapha Chellali     (LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria)
Maryam Hajjari     (Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R., Iran, Islamic Republic of)

Abstract


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

Full Text:

PDF

References


  1. Abdollahzadeh Ahangar H., Amjadi J., Chellali M., Nazari-Moghaddam S., Sheikholeslami S.M. Total Roman reinforcement in graphs. Discuss. Math. Graph Theory, 2019. Vol. 39, No. 4. P. 787–803. DOI: 10.7151/dmgt.2108
  2. Abdollahzadeh Ahangar H., Mirmehdipour S.R. Bounds on the restrained Roman domination number of a graph. Commun. Comb. Optim., 2016. Vol. 1, No. 1. P. 75–82. DOI: 10.22049/CCO.2016.13556
  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., 2017. Vol. 217. P. 394–404. DOI: 10.1016/j.dam.2016.09.043
  4. Amjadi J., Sadeghi H. Double Roman reinforcement number in graphs. AKCE Int. J. Graphs Comb., 2021. Vol. 18, No. 3. P. 191–199. DOI: 10.1080/09728600.2021.1997557
  5. Ebrahimi N., Amjadi J., Chellali M., Sheikholeslami S.M. Quasi-total Roman reinforcement in graphs. AKCE Int. J. Graphs Comb., 2022. In press. DOI: 10.1080/09728600.2022.2158051
  6. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completness. Freeman: San Francisco, 1979. 340 p.
  7. Hao G., Sheikholeslami S.M., Wei S. Italian reinforcement number in graphs. IEEE Access, 2019. Vol. 7. Art. no. 184448. DOI: 10.1109/ACCESS.2019.2960390
  8. Haynes T.W., Hedetniemi S.T., Slater P.J. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, 1998. 446 p. DOI: 10.1201/9781482246582
  9. Jafari Rad N., Sheikholeslami S.M. Roman reinforcement in graphs. Bull. Inst. Combin. Appl., 2011. Vol. 61. P. 81–90.
  10. Kok J., Mynhardt C.M. Reinforcement in graphs. Congr. Numer., 1990. Vol. 79. P. 225–231.
  11. Pushpam P.R.L., Padmapriea S. Restrained Roman domination in graphs. Trans. Comb., 2015. Vol. 4, No. 1. P. 1–17. DOI: 10.22108/TOC.2015.4395
  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., 2023. Vol. 438. Art. no. 127554. DOI: 10.1016/j.amc.2022.127554
  13. Shahbazi L., Abdollahzadeh Ahangar H., Khoeilar R., Shekholeslami S.M. Total k-rainbow reinforcement number in graphs. Discrete Math. Algorithms Appl., 2021. Vol. 13, No. 1. Art. no. 2050101. DOI: 10.1142/S1793830920501013
  14. Siahpour F., Abdollahzadeh Ahangar H., Sheikholeslami S.M. Some progress on the restrained Roman domination. Bull. Malays. Math. Sci. Soc., 2021. Vol. 44, No. 7. P. 733–751. DOI: 10.1007/s40840-020-00965-0
  15. Volkmann L. Remarks on the restrained Italian domination number in graphs. Commun. Comb. Optim., 2023. Vol. 8, No. 1. P. 183–191. DOI: 10.22049/CCO.2021.27471.1269
  16. Volkmann L. Restrained double Italian domination in graphs. Commun. Comb. Optim., 2023. Vol. 8, No. 1. P. 1–11. DOI: 10.22049/CCO.2021.27334.1236




DOI: http://dx.doi.org/10.15826/umj.2022.2.007

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.