Triple Roman domination subdivision number in graphs (Q6046760)

For a graph \(G=(V,E)\), a function \(f:V(G)\mapsto \{0,1,2,3,4\}\) is called a triple Roman domination function if \(f(AN[v])\geq |AN(v)|+3\) for any \(v\in V(G)\) with \(f(v)<3\), where \(AN(v)=\{w\in N(v)|\ f(w)\geq 1\}\) and \(AN[v]=AN(v)\cup\{v\}\). Let \(\omega(f)=\sum_{v\in V} f(v)\). The triple Roman domination number, denoted by \(\gamma_{[3R]}(G)\), is the \(\min\{\omega(f): f \text{ is a triple Roman domination function on }G\}\). The triple Roman domination subdivision number \(sd_{[3R]}(G)\) of a graph \(G\) is the minimum number of edges that must be subdivided (each edge in \(G\) can be subdivided at most once) to increase the triple Roman domination number. In the paper, the authors show that the decision problem associated with \(sd_{[3R]}(G)\) is NP-hard, and establish upper bounds on \(sd_{[3R]}(G)\) for a general graph \(G\).