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

Let \(G\) be a graph and let \(\{V_0,V_1,\dots, V_k\}\) be a partition of \(V(G)\) for some positive integer \(k\). Further, every vertex \(v\in V_i\) receives a label \(f(v)=i\) for every \(i\in\{0,1,\dots,k\}\). The weight of \(v\in V(G)\) is then \(w(v)=\sum_{u\in N(v)}f(u)\) where \(N(u)\) denotes the open neighborhood of \(u\in V(G)\) and the weight of \(G\) is \(w(G)=\sum_{v\in V(G)}f(v)\). The labeling \(f\) induced by the mentioned partition is called a Roman \(\{k\}\)-labeling if \(g(v)\geq k\) for every \(v\in V_0\). The Roman \(\{k\}\)-domination number \(\gamma_{\{Rk\}}(G)\) of \(G\) is the minimum weight of a Roman \(\{k\}\)-labeling of \(G\). The main results of this paper are fully described trees for which \(\gamma_{\{Rk\}}(T)=k\gamma(T)\) holds (here \(\gamma (T)\) represents the usual domination number of \(T\)) and complexity results on \(\gamma_{\{Rk\}}(G)\).