Roman {K}-domination In Trees And Complexity Results For Some Classes Of Graphs

We study Roman {k}-dominating functions(also called weak{k}-dominating functions)on a graph G with vertex set V for a positive integer k:a variant of{f}-dominating functions7,generations of Roman {2}-dominating functions on G and the characteristic functions of dominating sets of G,respectively,which unify classic dominating parameters with certain Roman dominating parameter-s on G.Let k?1 be an integer7,a function ?:V? {0,1,...,k} defined on V is called a Roman {k}-dominating function if for every vertex v ? V with f(v)= 0,?n?N(v)f(u)?k,where N(v)is the neighborhood of v in G.The minimum value ?n?V ?(u)for a Roman {k}-dominating function ? on G is called the Roman {k}-domination number of G,denoted by ?{Rk}(G).Note that?{R1}(G)and ?{R1}(G)are the usual domination number ?(G)and the Roman{2}-domination number,respectively.We first present some basic properties of?{Rk)(G),and bounds on ?{Rk}(G)with respect to other domination parameters,including ?(Rk)(G)?k?(G)and then show one of our main results:character-izing the trees T in which ?{Rk}(T)= k ?(T)generalizing Henning and kloster-meyer's results on the Roman {2}-domination number[Discrete Appl.Math.217(2017)557-564].Secondly,we consider the Roman {k}-domination number on graph products.Finally,we show that for every fixed k?Z1,associated decision problem for the Roman {k}-domination is NP-complete,even for bipartite planar graphs,chordal bipartite graphs and undirected path graphs.