Outer-independent total Roman domination in graphs

Abstract

Given a graph $G$ with vertex set $V$, a function $f:V\rightarrow \{0,1,2\}$ is an outer-independent total Roman dominating function on $G$ if \begin{itemize} \item every vertex $v\in V$ for which $f(v)=0$ is adjacent to at least one vertex $u\in V$ such that $f(u)=2$, \item every vertex $x\in V$ for which $f(x)\ge 1$ is adjacent to at least one vertex $y\in V$ such that $f(y)\ge 1$, and \item any two different vertices $a,b$ for which $f(a)=f(b)=0$ are not adjacent. \end{itemize} The minimum weight $\omega(f)=\sum_{w\in V}f(w)$ of any outer-independent total Roman dominating function on $G$ is the outer-independent total Roman domination number, $\gamma_{oitR}(G)$, of $G$. In this article, we introduce the concepts above and begin with the study of its combinatorial and computational properties. For instance, we give several closed relationships between this parameter and other ones related with domination in graphs. We prove that computing $\gamma_{oitR}$ of a graph $G$ is an NP-hard problem. In addition, we present some closed formulae for $\gamma_{oitR}(G)$ in the cases $G$ represents some special families of graphs.