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\}$$ { 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\ge 1$$ k ≥ 1 be an integer, and a function $$f:V \rightarrow \{0,1,\dots ,k\}$$ f : V → { 0 , 1 , ⋯ , k } defined on V called a Roman $$\{k\}$$ { k } -dominating function if for every vertex $$v\in V$$ v ∈ V with $$f(v)=0$$ f ( v ) = 0 , $$\sum _{u\in N(v)}f(u)\ge k$$ ∑ u ∈ N ( v ) f ( u ) ≥ k , where N(v) is the open neighborhood of v in G. The minimum value $$\sum _{u\in V}f(u)$$ ∑ u ∈ V f ( u ) for a Roman $$\{k\}$$ { k } -dominating function f on G is called the Roman $$\{k\}$$ { k } -domination number of G, denoted by $$\gamma _{\{Rk\}}(G)$$ γ { R k } ( G ) . We first present bounds on $$\gamma _{\{Rk\}}(G)$$ γ { R k } ( G ) in terms of other domination parameters, including $$\gamma _{\{Rk\}}(G)\le k\gamma (G)$$ γ { R k } ( G ) ≤ k γ ( 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\in \mathbb {Z_{+}}$$ k ∈ Z + , associated decision problem for the Roman $$\{k\}$$ { k } -domination is NP-complete, even for bipartite planar graphs, chordal bipartite graphs and undirected path graphs.