|
Abstract
|
A double Roman dominating function (DRDF) on a graph G ¼ ðV; EÞ is a function f : VðGÞ ! f0; 1; 2; 3g 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 cdRð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,
cdRðTÞ2cðTÞ þ 1; where cð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 cdRðTÞ ¼ 2cðTÞ þ 2.
|