algorithmic complexity of triple roman dominating functions on graphs

Given a graph g = (v;e), a function f : v ! f0; 1; 2; 3; 4g is a tripleroman dominating function (trdf) of g, for each vertex v 2 v , (i) if f(v) = 0,then v must have either one neighbour in v4, or either two neighbours in v2 [ v3 (oneneighbour in v3) or either three neighbours in v2, (ii) if f(v) = 1, then v must haveeither one neighbour in v3 [ v4 or either two neighbours in v2, and if f(v) = 2, then vmust have one neighbour in v2 [ v3 [ v4. the triple roman domination number of gis the minimum weight of an trdf f of g, where the weight of f is ∑ 𝑣(v). thetriple roman domination problem is to compute the triple roman domination numberof a given graph. in this paper, we study the triple roman domination problem. weshow that the problem is np-complete for the star convex bipartite and the combconvex bipartite graphs and is apx-complete for graphs of degree at most 4. wepropose a linear-time algorithm for computing the triple roman domination number ofproper interval graphs. we also give an (2h(δ(g) + 1) - 1)-approximation algorithmfor solving the problem for any graph g, where δ(g) is the maximum degree of g andh(d) denotes the first d terms of the harmonic series. in addition, we prove that for any > 0 there is no (1/4) ln jv j-approximation polynomial-time algorithm for solvingthe problem on bipartite and split graphs, unless np dtime (jv jo(log log jv j)).