algorithmic aspects of quasi-total roman domination in graphs

for a simple, undirected, connected graph 𝐺( 𝑉,𝐸 ), a function 𝑓: 𝑉(𝐺) → {0, 1, 2} which satisfies the following conditions is called a quasi-total roman dominating function (qtrdf) of 𝐺 with weight 𝑓(𝑉(𝐺))=∑𝑣 ϵ 𝑉(𝐺)} 𝑓(𝑣) . c1). every vertex u in 𝑉(𝐺) for which 𝑓(𝑢) = 0 must be adjacent to at least one vertex 𝑉 with 𝑓(𝑣) = 2 , and     c2). every vertex 𝑢 ϵ 𝑉(𝐺) for which 𝑓(𝑢) = 2 must be adjacent to at least one vertex 𝑉 with 𝑓(𝑣) geq 1. for a graph 𝐺, the smallest possible weight of a qtrdf of 𝐺 denoted gamma_{qtr}(𝐺) is known as the textit{quasitotal roman domination number} of 𝐺.    the problem of determining 𝑟𝑞𝑟𝑅(𝐺) of a graph 𝐺 is called minimum quasitotal roman domination problem (mqtrdp). in this paper, we show that the problem of determining whether 𝐺 has a qtrdf of weight at most l is npcomplete for split graphs, star convex bipartite graphs, comb convex bipartite graphs  and planar graphs. on the positive side, we show that mqtrdp  for threshold graphs, chain graphs and bounded treewidth graphs is linear time solvable. finally, an integer linear programming  formulation for mqtrdp is presented.