Strong equality of Roman and perfect Roman Domination in trees

¹ Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, P.R. China
² Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
³ Department of Mathematics, Yasouj University, Yasouj, Iran

^* Corresponding author: s.m.sheikholeslami@azaruniv.ac.ir

Received: 18 July 2020
Accepted: 9 January 2022

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 v for which f(v) = 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 v for which f(v) = 2. The (perfect) Roman domination number γ_R(G) (γ^p_R(G)) is the minimum weight of an (perfect) Roman dominating function on G. We say that γ^p_R(G) strongly equals γ_R(G), denoted by γ^p_R(G) ≡ γ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 G, it is NP-hard to decide whether γ^pR(G) = γR(G) and also we provide a constructive characterization of trees T with γ^pR(T) ≡ γR(T).