Hadi Rahbani - Department of Mathematics Shahrood University of Technology Shahrood, Iran

Let be a simple graph and{۰,۱,۲} be a function. Given a vertex of graph with if all neighbors of have zero weights, then 𝑢 is called undefended with respect to 𝑓. Furthermore, if every vertex with=۰ has a neighbor with and the function {۰,۱,۲} with=۱has no undefended vertex, then 𝑓 is called a weak Roman dominating function. Also, the function is a perfect Roman dominating function if every vertex with =۰ is adjacent to exactly one vertex for which=۲. Let the weight of be . The weak (resp., perfect) Roman domination number, denoted by(resp., is the minimum weight of the weak (resp., perfect) Roman dominating function in_xDC۳A_. In this paper we show that for a given graph it is NP-hard to decide whether 𝛾

Perfect Roman dominating function, Weak Roman dominating function, Graphs, Complexity.