Double Roman domination in trees

A double Roman dominating function on a graph G is a function f:V(G)→{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=3 or two vertices v1 and v2 for which f(v1)=f(v2)=2, and every vertex u for which f(u)=1 is adjacent to at least one vertex v for which f(v)≥2. The weight of a double Roman dominating function f is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdR(G) of G. Beeler et al. (2016) [6] showed that 2γ(G)≤γdR(G)≤3γ(G) and showed that 2γ(T)+1≤γdR(T)≤3γ(T) for any non-trivial tree T and posed a problem that if it is possible to construct a polynomial algorithm for computing the value of γdR(T) for any tree T. In this paper, we answer this problem by giving a linear time algorithm to compute the value of γdR(T) for any tree T. Moreover, we give characterizations of trees with 2γ(T)+1=γdR(T) and γdR(T)+1=2γR(T).