Perfect Roman domination in graphs

Abstract A perfect Roman dominating function on a graph G is a function f : V ( G ) ⟶ { 0 , 1 , 2 } having the property that for every vertex u with f ( u ) = 0 , there exists exactly one vertex v such that u v ∈ E ( G ) and f ( v ) = 2 . The weight of f, denoted by w ( f ) , is the value ∑ v ∈ V ( G ) f ( v ) . Given a graph G and a positive integer k, the perfect Roman domination problem is to decide whether there is a perfect Roman dominating function f on G such that w ( f ) is at most k. In this paper, we first show that the perfect Roman domination problem is NP -complete for chordal graphs, planar graphs, and bipartite graphs. Then we present polynomial time algorithms for computing a perfect Roman dominating function with minimum weight in block graphs, cographs, series-parallel graphs, and proper interval graphs.