Trees with Double Roman Domination Number Twice the Domination Number Plus Two

摘要

A double Roman dominating function (DRDF) on a graph G=(V,E) is a function f:V(G){0,1,2,3} such that (i) every vertex v with f(v)=0 is adjacent to at least two vertices assigned a 2 or to at least one vertex assigned a 3, (ii) every vertex v with f(v)=1 is adjacent to at least one vertex w with f(w)2. The weight of a DRDF is the sum of its function values over all vertices. The double Roman domination number dR(G) equals the minimum weight of a double Roman dominating function on G. Beeler, Haynes and Hedetniemi showed that for every non-trivial tree T, dR(T)2(T)+1, where (T) is the domination number of T. A characterization of extremal trees attaining this bound was given by three of us. In this paper, we characterize all trees T with dR(T)=2(T)+2.