Frontiers in Applied Mathematics and Statistics (Feb 2021)
On the Outer-Independent Double Roman Domination of Graphs
Abstract
An outer-independent double Roman dominating function (OIDRDF) of a graph G is a function h:V(G)→{0,1,2,3} such that i) every vertex v with f(v)=0 is adjacent to at least one vertex with label 3 or to at least two vertices with label 2, ii) every vertex v with f(v)=1 is adjacent to at least one vertex with label greater than 1, and iii) all vertices labeled by 0 are an independent set. The weight of an OIDRDF is the sum of its function values over all vertices. The outer-independent double Roman domination number γoidR (G) is the minimum weight of an OIDRDF on G. It has been shown that for any tree T of order n ≥ 3, γoidR (T) ≤ 5n/4 and the problem of characterizing those trees attaining equality was raised. In this article, we solve this problem and we give additional bounds on the outer-independent double Roman domination number. In particular, we show that, for any connected graph G of order n with minimum degree at least two in which the set of vertices with degree at least three is independent, γoidR (T) ≤ 4n/3.
Keywords
