Perfect Roman {3}-Domination in Graphs: Complexity and Bound of Perfect Roman {3}-Domination Number of Trees

A perfect Roman 3-dominating function on a graph G=V,E is a function f:V⟶0,1,2,3 having the property that if fv=0, then ∑u∈Nvfu=3, and if fv=1, then ∑u∈Nvfu=2 for any vertex v∈V. The weight of a perfect Roman 3-dominating function f is the sum ∑v∈Vfv. The perfect Roman 3-domination number of a graph G, denoted by γR3pG, is the minimum weight of a perfect Roman 3-dominating function on G. In this paper, we initiate the study of a perfect Roman 3-domination, and we show that the decision problem associated with a perfect Roman 3-domination is NP-complete for bipartite graphs. We also prove that if T is a tree of order n≥2, then γR3pT≤3n/2 and characterize trees achieving this bound, and we give an infinity set of trees T of order n for which γR3pT approaches this bound as n goes to infinity. Finally, we give the best upper bound of γR3pG for some classes of graphs including regular, planar, and split graphs in terms of the order of the graphs.