Complexity of signed total $k$-Roman domination problem in graphs

Abstract

Let $G$ be a simple graph with finite vertex set $V(G)$ and $S=\{-1,1,2\}$. A signed total Roman $k$-dominating function (STRkDF) on a graph $G$ is a function $f:V(G)\to S$ such that (i) any vertex $y$ with $f(y)=-1$ is adjacent to at least one vertex $t$ with $f(t)=2,$ (ii) $\sum_{t\in N(y)}f(t)\geq k$ holds for any vertex $y$. The $weight$ of an STRkDF $f$, denoted by $\omega(f)$, is $\sum_{y\in V(G)}f(y)$, and the minimum weight of an STRkDF is the signed total Roman k-domination number,$\gamma_{stR}^k(G),$ of $G$. In this article, we prove that the decision problem for the signed total Roman $k$-domination is NP-complete on bipartite and chordal graphs for $k\in\{1, 2\}$.

Keywords

• signed total roman k-dominating function
• signed total roman k-domination number
• complexity