Algorithmic and complexity aspects of problems related to total Roman domination for graphs

A function $$f:V(G)\rightarrow \{0,1,2\}$$f:V(G)→{0,1,2} is a Roman dominating function (RDF) if every vertex u for which $$f(u)=0$$f(u)=0 is adjacent to at least one vertex v for which $$f(v)=2$$f(v)=2. The weight of a Roman dominating function is the value $$f(V(G))=\sum _{u \in V}f(u)$$f(V(G))=∑u∈Vf(u). The Roman domination number of a graph G, denoted by $$\gamma _{R}(G)$$γR(G), is the minimum weight of a Roman dominating function on G. A connected (respectively, total) Roman dominating function is an RDF f such that the vertices with non-zero labels under f induce a connected graph (respectively, a subgraph with no isolated vertex). The connected (respectively, total) Roman domination number of a graph G, denoted by $$\gamma _{cR}(G)$$γcR(G) (respectively, $$\gamma _{tR}(G)$$γtR(G)) is the minimum weight of a connected (respectively, total) RDF of G. It this paper we first study the complexity issue of the problems posed in [H. Abdollahzadeh Ahangar, M. A. Henning, V. Samodivkin and I. G. Yero, Total Roman domination in graphs, Appl. Anal. Discret. Math. 10 (2016), 501–517], and show that the problem of deciding whether $$\gamma _{tR}(G)=2\gamma (G)$$γtR(G)=2γ(G), $$\gamma _{tR}(G)=2\gamma _t(G)$$γtR(G)=2γt(G) or $$\gamma _{tR}(G)=3\gamma (G)$$γtR(G)=3γ(G) is NP-hard even when restricted to chordal or bipartite graphs. Then, we give a linear algorithm that decides whether $$\gamma _{tR}(G)=2\gamma (G)$$γtR(G)=2γ(G), $$\gamma _{tR}(G)=2\gamma _t(G)$$γtR(G)=2γt(G) or $$\gamma _{tR}(G)=3\gamma (G)$$γtR(G)=3γ(G), if G is a tree or a unicyclic graph.