مشخصات پژوهش

For a graph G = (V,E), a triple Roman domination function is a function f : V (G) −→ {0, 1, 2, 3, 4} having the property that for any vertex v ∈ V (G), if f(v) < 3, then f(AN[v]) ≥ |AN(v)|+3, where AN(v) = {w ∈ N(v) | f(w) ≥ 1} and AN[v] = AN(v)∪{v}. The weight of a triple Roman dominating function f is the value !(f) = P v2V (G) f(v). The triple Roman domination number of G, denoted by [3R](G), equals the minimum weight of a triple Roman dominating 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) in order to increase the triple Roman domination number. In this paper, we first show that the decision problem associated with sd [3R] (G) is NP-hard and then establish upper bounds on the triple Roman domination subdivision number for arbitrary graphs.