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

Abstract

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\left(G\right)\to \{0,1,2,3\}$ having the property that (i) ${\sum }_{w\in N\left(v\right)}f\left(w\right)\ge 3$ if $f\left(v\right)=0$; (ii) ${\sum }_{w\in N\left(v\right)}f\left(w\right)\ge 2$ if $f\left(v\right)=1$; and (iii) every vertex v with $f\left(v\right)\ne 0$ has a neighbor u with $f\left(u\right)\ne 0$ for every vertex $v\in V\left(G\right)$. The weight of a TR3DF f is the sum $f\left(V\right)={\sum }_{v\in V\left(G\right)}f\left(v\right)$ and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by ${\gamma }_{t\{R3\}}\left(G\right)$. 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 ${\gamma }_{t\{R3\}}$ for trees.