Global triple Roman dominating function (Q2127628): Difference between revisions

A triple Roman dominating function (TRD-function) of a graph \(G\) is a function \(f: V(G) \rightarrow \{0, 1, 2, 3, 4\}\) such that if \(f(v) < 3\), then \(f(AN[v]) \ge |AN(v)| + 3\), where \(AN(v)\) is the set of neighbors of \(v\) assigned a non-zero value under \(f\). The minimum weight of a TRD-function on \(G\) is the triple Roman domination number of \(G\), denoted by \(\gamma_{[3R]}(G)\). A global triple Roman dominating function is a TRD-function for both \(G\) and its complement; the global triple Roman domination number is denoted by \(\gamma_{g[3R]}(G)\). It is proved that the global triple Roman dominating problem is NP-complete for bipartite and chordal graphs. Numerous bounds on \(\gamma_{[3R]}(G)\) and \(\gamma_{g[3R]}(G)\) are given and relations between them studied. For instance, if the diameter of \(G\) is at least \(6\) or its radius is \(4\) or \(5\), then \(\gamma_{[3R]}(G) = \gamma_{g[3R]}(G)\), while if \(G\) is triangle-free, then \(\gamma_{g[3R]}(G) \le \gamma_{[3R]}(G) + 4\).