|
Abstract
|
A double Roman dominating function (DRDF) on a graph G=(V,E) is a function f:V→{0,1,2,3} having the property that if f(v)=0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w)=3 , and if f(v)=1 , then vertex v must have at least one neighbor w with f(w)≥2 . The weight of a DRDF f is the value f(V)=∑u∈Vf(u) . The double Roman domination number γdR(G) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality γdR(G)≤6n5 and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, γdR(G)≤8n7 .
|