Computational Complexity of Outer-Independent Total and Total Roman Domination Numbers in Trees

An outer-independent total dominating set (OITDS) of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$ , and the set $V(G)\setminus D$ is independent. The outer-independent total domination number of a graph $G$ , denoted by $\gamma _{oit}(G)$ , is the minimum cardinality of an OITDS of $G$ . An outer-independent total Roman dominating function (OITRDF) on a graph $G$ is a function $f: V(G) \rightarrow \{0, 1, 2\}$ satisfying the conditions that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$ , every vertex $x$ with $f(x)\geq 1$ is adjacent to at least one vertex $y$ with $f(y)\geq 1$ , and any two different vertices $a,b$ with $f(a)=f(b)=0$ are not adjacent. The minimum weight $\omega (f) =\sum _{v\in V(G)}f(v)$ of any OITRDF $f$ for $G$ is the outer-independent total Roman domination number of $G$ , denoted by $\gamma _{oitR}(G)$ . A graph $G$ is called an outer-independent total Roman graph (OIT-Roman graph) if $\gamma _{oitR}(G)=2\gamma _{oit}(G)$ . In this paper, we propose dynamic programming algorithms to compute the outer-independent total domination number and the outer-independent total Roman domination number of a tree, respectively. Moreover, we characterize all OIT-Roman graphs and give a linear time algorithm for recognizing an OIT-Roman graph.