|
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) → S such that (i) any
vertex y with f(y) = −1 is adjacent to at least one vertex t with f(t) = 2, (ii) P
t∈N(y)
f(t) ≥ k holds for
any vertex y. The weight of an STRkDF f , denoted by ω(f), is P
y∈V(G)
f(y), and the minimum weight
of an STRkDF is the signed total Roman k-domination number, γk
stR(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 ∈ {1, 2}.
|