On [k] -Roman domination in graphs

For an integer k = 1, let f be a function that assigns labels from the set {0,1, ... , k + 1} to the vertices of a simple graph G = (V, E). The active neighborhood AN(v) of a vertex v ? V(G) with respect to f is the set of all neighbors of v that are assigned non-zero values under f. A [k]-Roman dominating function ([k]-RDF) is a function f : V(G) -? {0,1, 2, ... , k + 1} such that for every vertex v ? V(G) with f(v) < k, we have S-u?N[v] f(u) = |AN(v)| + k. The weight of a [k]-RDF is the sum of its function values over the whole set of vertices, and the [k]-Roman domination number ?[kR](G) is the minimum weight of a [k]-RDF on G. In this paper we determine various bounds on the [k]-Roman domination number. In particular, we show that for any integer k = 2 every connected graph G of order n = 3, satisfies ?[kR](G) = (2k+1/4 n, and we characterize the graphs G attaining this bound. Moreover, we show that if T is a nontrivial tree, then ?[kR](T) = k? (T) + 1 for every integer k = 2 and we characterize the trees attaining the lower bound. Finally, we prove the NP-completeness of the [k]-Roman domination problem in bipartite and chordal graphs.