Algorithmic and complexity aspects of problems related to total Roman domination for graphs (Q2307496): Difference between revisions

A function \(f : V(G)\to \{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 \(\sum_{u\in V} f (u)\). 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 graph with no isolated vertex). The connected (respectively, total) Roman domination number of a graph \(G\), denoted by \(\gamma_{cR}(G)\) (respectively, \(\gamma_{t R}(G)\)) is the minimum weight of a connected (respectively, total) RDF of \(G\). It was shown that \(2\gamma (G) \le \gamma_{t R}(G) \le 3\gamma(G)\) and \(\gamma_t (G) \le \gamma_{t R}(G) \le 2\gamma_t (G)\). In this paper, the authors considered the problems posed in [\textit{H. A. Ahangar} et al., Appl. Anal. Discrete Math. 10, No. 2, 501--517 (2016; Zbl 1461.05151)], and showed that the problem of deciding whether \(\gamma_{t R}(G) = 2\gamma(G)\), \(\gamma_{t R}(G) = 2\gamma_t(G)\) or \(\gamma_{tR}(G) = 3\gamma (G)\) is NP-hard even when restricted to chordal or bipartite graphs. Moreover, they proved the following results. (1) There is a linear algorithm that computes the total Roman domination number of a given tree in linear time. Also, given a tree \(T\), there is a linear algorithm that decides whether \(\gamma_{t R}(T ) = 2\gamma (T )\), \(\gamma_{t R}(T ) = 3\gamma (T )\) or \(\gamma_{t R}(T ) = 2\gamma_t (T )\). (2) There is a linear algorithm that computes the (total, total Roman) domination number of a given unicyclic graph in linear time. Furthermore, given an unicyclic graph \(U\), there is a linear algorithm that decides whether \(\gamma_{t R}(U ) = 2\gamma (U )\), \(\gamma_{t R}(U ) = 3\gamma (U )\) or \(\gamma_{t R}(U ) = 2\gamma_t (U )\).