On the signed Roman k-domination: Complexity and thin torus graphs

A signed Roman k-dominating function on a graph G=(V(G),E(G)) is a function f:V(G)→{−1,1,2} such that (i) every vertex u with f(u)=−1 is adjacent to at least one vertex v with f(v)=2 and (ii) ∑x∈N[w]f(x)≥k holds for any vertex w. The weight of f is ∑u∈V(G)f(u), the minimum weight of a signed Roman k-dominating function is the signed Roman k-domination number γsRk(G) of G. It is proved that determining the signed Roman k-domination number of a graph is NP-complete for k∈{1,2}. Using a discharging method, the values γsR2(C3□Cn) and γsR2(C4□Cn) are determined for all n.