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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2414-3952 |