On perfect Roman domination number in trees: complexity and bounds

A perfect Roman dominating function on a graph $$G =(V,E)$$ G = ( V , E ) is a function $$f: V \longrightarrow \{0, 1, 2\}$$ f : V ⟶ { 0 , 1 , 2 } satisfying the condition that every vertex u with $$f(u) = 0$$ f ( u ) = 0 is adjacent to exactly one vertex v for which $$f(v)=2$$ f ( v ) = 2 . The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted by $$\gamma _{R}^{p}(G)$$ γ R p ( G ) , is the minimum weight of a perfect Roman dominating function in G. In this paper, we first show that the decision problem associated with $$\gamma _{R}^{p}(G)$$ γ R p ( G ) is NP-complete for bipartite graphs. Then, we prove that for every tree T of order $$n\ge 3$$ n ≥ 3 , with $$\ell $$ ℓ leaves and s support vertices, $$\gamma _R^P(T)\le (4n-l+2s-2)/5$$ γ R P ( T ) ≤ ( 4 n - l + 2 s - 2 ) / 5 , improving a previous bound given in Henning et al. (Discrete Appl Math 236:235–245, 2018).