An improved upper bound on the independent double Roman domination number of trees

Abstract

AbstractFor a graph [Formula: see text] an independent double Roman dominating function (IDRDF) is a function [Formula: see text] having the property that: (i) every vertex [Formula: see text] with f(v) = 0 has a neighbor u with f(u) = 3 or at least two neighbors x and y such that [Formula: see text] (ii) every vertex [Formula: see text] with f(v) = 1 has at least one neighbor assigned a 2 or 3 under f; (iii) the set of vertices assigned non-zero values under f is independent. The weight of an IDRDF is the sum of its values overs all vertices, and the independent double Roman domination number [Formula: see text] is the minimum weight of an IDRDF on [Formula: see text] In this article, we show that for every tree T of order [Formula: see text] where s(T) is the number of support vertices of T, improving the [Formula: see text]-upper bound established in [Maimani et al. Independent double Roman domination in graphs, Bulletin of the Iranian Mathematical Society, 46 (2020) 543–555]. Moreover, we characterize the trees T of order [Formula: see text] with [Formula: see text]

Keywords

• Independent double Roman domination
• trees
• 05C69
• 05C05