RT journal article
T1 Outer-independent total Roman domination in graphs
A1 Cabrera Martínez, Abel
A1 Kuziak, Dorota
A1 González Yero, Ismael
A2 Estadística e Investigación Operativa
A2 Matemáticas
K1 outer-independent total Roman domination
K1 total Roman domination
K1 Roman domination
K1 total domination
K1 vertex independence
K1 vertex cover
AB 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.
PB Elsevier
SN 0166-218X
YR 2019
FD 2019-09-30
LK http://hdl.handle.net/10498/30892
UL http://hdl.handle.net/10498/30892
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 11-nov-2026