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

a. Poureidi | Nader Jafari Rad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137173
Date :  2020/09/24
Publish in :    Journal of Combinatorial Optimization

Link :  https://link.springer.com/article/10.1007/s10878-019-00514-x
Keywords :Dominating set Total dominating set Total Roman dominating function Algorithm 3-SAT

Abstract :

---

A function f:V(G)→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))=∑u∈Vf(u). The Roman domination number of a graph G, denoted by γ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 γcR(G) (respectively, γ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 γtR(G)=2γ(G), γtR(G)=2γt(G) or γtR(G)=3γ(G) is NP-hard even when restricted to chordal or bipartite graphs. Then, we give a linear algorithm that decides whether γtR(G)=2γ(G), γtR(G)=2γt(G) or γtR(G)=3γ(G), if G is a tree or a unicyclic graph.