|
Abstract
|
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.
|