Name
Abstract | ||
|---|---|---|
A Roman dominating function (RD-function) on a graph G = (V,E) is a function f : V -> {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex u for which f(u) = 2. An Roman dominating function f in a graph G is perfect Roman dominating function (PRD-function) if every vertex u with f (u) = 0 is adjacent to exactly one vertex u for which f (u) = 2. The (perfect) Roman domination number gamma(R)(G) (gamma(p)(R)(G)) is the minimum weight of an (perfect) Roman dominating function on G. We say that gamma(p)(R)(G) strongly equals gamma(R)(G), denoted by gamma(p)(R)(G) equivalent to gamma(R)(G), if every RD-function on G of minimum weight is a PRD-function. In this paper we show that for a given graph.., it is NP-hard to decide whether gamma(p)(R)(G) equivalent to gamma(R)(G) and also we provide a constructive characterization of trees T with gamma(p)(R)(T) equivalent to gamma(R)(T). |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1051/ro/2022005 | RAIRO-OPERATIONS RESEARCH |
Keywords | DocType | Volume |
Perfect Roman dominating function, Roman dominating function | Journal | 56 |
Issue | ISSN | Citations |
1 | 0399-0559 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zehui Shao | 1 | 119 | 30.98 |
| Saeed Kosari | 2 | 0 | 2.70 |
| Hadi Rahbani | 3 | 0 | 0.34 |
| Mehdi Sharifzadeh | 4 | 0 | 0.34 |
| Seyed Mahmoud Sheikholeslami | 5 | 0 | 2.37 |