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.