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

A function \(f:V(G)\rightarrow \{0,1,2\}\) is a Roman dominating function (RDF) if every vertex u for which \(f(u)=0\) is adjacent to at least one vertex v for which \(f(v)=2\). The weight of a Roman dominating function is the value \(f(V(G))=\sum _{u \in V}f(u)\). The Roman domination number of a graph G, denoted by \(\gamma _{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)\) (respectively, \(\gamma _{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)\), \(\gamma _{tR}(G)=2\gamma _t(G)\) or \(\gamma _{tR}(G)=3\gamma (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)\), \(\gamma _{tR}(G)=2\gamma _t(G)\) or \(\gamma _{tR}(G)=3\gamma (G)\), if G is a tree or a unicyclic graph.