Roman {k}-domination in trees and complexity results for some classes of graphs

In this paper, we study Roman {k}-dominating functions on a graph G with vertex set V for a positive integer k: a variant of {k}-dominating functions, generations of Roman {2}-dominating functions and the characteristic functions of dominating sets, respectively, which unify classic domination parameters with certain Roman domination parameters on G. Let k >= 1 be an integer, and a function f : V -> {0, 1,..., k} defined on V called a Roman {k}-dominating function if for every vertex v is an element of V with f (v) = 0, Sigma(u is an element of N(v)) f (u) >= k, where N(v) is the open neighborhood of v in G. The minimum value Sigma(u is an element of V) f (u) for a Roman {k}-dominating function f on G is called the Roman {k}-domination number of G, denoted by gamma({Rk})(G). We first present bounds on gamma({Rk}) (G) in terms of other domination parameters, including gamma({Rk})(G) <= k gamma (G). Secondly, we show one of our main results: characterizing the trees achieving equality in the bound mentioned above, which generalizes M.A. Henning and W.F. klostermeyer's results on the Roman {2}-domination number (Henning and Klostermeyer in Discrete Appl Math 217:557-564, 2017). Finally, we show that for every fixed k is an element of Z(+), associated decision problem for the Roman {k}-domination is NP-complete, even for bipartite planar graphs, chordal bipartite graphs and undirected path graphs.