مشخصات پژوهش

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}.