Total Roman {3}-Domination: The Complexity and Linear-Time Algorithm for Trees

For a simple graph G = ( V , E ) with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function f : V ( G ) → { 0 , 1 , 2 , 3 } having the property that (i) ∑ w ∈ N ( v ) f ( w ) ≥ 3 if f ( v ) = 0 ; (ii) ∑ w ∈ N ( v ) f ( w ) ≥ 2 if f ( v ) = 1 ; and (iii) every vertex v with f ( v ) ≠ 0 has a neighbor u with f ( u ) ≠ 0 for every vertex v ∈ V ( G ) . The weight of a TR3DF f is the sum f ( V ) = ∑ v ∈ V ( G ) f ( v ) and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by γ t { R 3 } ( G ) . In this paper, we show that the total Roman {3}-domination problem is NP-complete for planar graphs and chordal bipartite graphs. Finally, we present a linear-time algorithm to compute the value of γ t { R 3 } for trees.