RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS
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 is...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and Mechanics
2022-12-01
|
| Series: | Ural Mathematical Journal |
| Subjects: | |
| Online Access: | https://umjuran.ru/index.php/umj/article/view/458 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849412189242261504 |
|---|---|
| author | Saeed Kosari Seyed Mahmoud Sheikholeslami Mustapha Chellali Maryam Hajjari |
| author_facet | Saeed Kosari Seyed Mahmoud Sheikholeslami Mustapha Chellali Maryam Hajjari |
| author_sort | Saeed Kosari |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-486dfe6ad7684b3794f14a84b8cc3739 |
| institution | Kabale University |
| issn | 2414-3952 |
| language | English |
| publishDate | 2022-12-01 |
| publisher | Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and Mechanics |
| record_format | Article |
| series | Ural Mathematical Journal |
| spelling | doaj-art-486dfe6ad7684b3794f14a84b8cc37392025-08-20T03:34:31ZengUral Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and MechanicsUral Mathematical Journal2414-39522022-12-018210.15826/umj.2022.2.007165RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHSSaeed Kosari0Seyed Mahmoud Sheikholeslami1Mustapha Chellali2Maryam Hajjari3Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R.LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, BlidaDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R.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.https://umjuran.ru/index.php/umj/article/view/458restrained roman domination, restrained roman reinforcement |
| spellingShingle | Saeed Kosari Seyed Mahmoud Sheikholeslami Mustapha Chellali Maryam Hajjari RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS Ural Mathematical Journal restrained roman domination, restrained roman reinforcement |
| title | RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS |
| title_full | RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS |
| title_fullStr | RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS |
| title_full_unstemmed | RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS |
| title_short | RESTRAINED ROMAN REINFORCEMENT NUMBER IN GRAPHS |
| title_sort | restrained roman reinforcement number in graphs |
| topic | restrained roman domination, restrained roman reinforcement |
| url | https://umjuran.ru/index.php/umj/article/view/458 |
| work_keys_str_mv | AT saeedkosari restrainedromanreinforcementnumberingraphs AT seyedmahmoudsheikholeslami restrainedromanreinforcementnumberingraphs AT mustaphachellali restrainedromanreinforcementnumberingraphs AT maryamhajjari restrainedromanreinforcementnumberingraphs |