On computing total double Roman domination number of trees in linear time

Abstract

Let $G=(V,E)$ be a graph. A double<br />Roman dominating function (DRDF) on $G$ is a function<br />$f:Vto{0,1,2,3}$ such that for every vertex $vin V$<br />if $f(v)=0$, then either there is a vertex $u$ adjacent to $v$ with $f(u)=3$ or<br />there are vertices $x$ and $y$ adjacent to $v$ with $f(x)=f(y)=2$ and if $f(v)=1$, then there is a vertex $u$ adjacent to $v$ with<br />$f(u)geq2$.<br />A DRDF $f$ on $G$ is a total DRDF (TDRDF) if for any $vin V$ with $f(v)>0$ there is a vertex $u$ adjacent to $v$ with $f(u)>0$.<br />The weight of $f$ is the sum $f(V)=sum_{vin V}f<br />(v)$. The minimum weight of a TDRDF on $G$ is the total double Roman<br />domination number of $G$. In this paper, we give a linear algorithm to compute the<br />total double Roman domination number of a<br />given tree.