Perfect triple Roman domination (Q6930353)

The authors introduce perfect \([k]\)-Roman domination and focus on the case \(k=3\). For a labeling \(f:V(G)\to\{0,1,2,3,4\}\), the active neighborhood \(AN(v)\) consists of neighbors of \(v\) with nonzero labels. A perfect triple Roman dominating function satisfies, for every vertex \(v\) with \(f(v)<3\), \(\sum_{u\in N[v]} f(u)=|AN(v)|+3\). The corresponding invariant \(\gamma^{p}_{[3R]}(G)\) is the minimum weight \(\sum_{v\in V(G)} f(v)\).\N\NAlgorithmically, the decision problem for \(\gamma^{p}_{[3R]}(G)\) is shown to be NP-complete even for bipartite graphs. Exact values are determined for paths \(P_n\) and cycles \(C_n\), given by explicit (piecewise) formulas in terms of \(n\). For trees \(T\) of order \(n\ge 5\), the authors prove the sharp upper bound \(\gamma^{p}_{[3R]}(T)\le 2n-2\) and characterize the extremal trees attaining equality, namely healthy spiders, corona graphs of \(P_3\) and \(P_4\), and trees obtained from a corona of a tree by attaching one additional vertex to a support vertex. Several open problems are proposed.