Document Type : Research Paper

Author

• Abolfazl Poureidi

Department of Mathematics, Shahrood University of Technology Shahrood, Iran

Abstract

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

Keywords

• Total double Roman dominating function
• linear algorithm
• Dynamic programming
• Combinatorial optimization
• Tree