Institute of Mathematics

Abstract:  For a graph $G=(V,E)$, a double Roman dominating function is a function $f\colon V\rightarrow\{0,1,2,3\}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must have at least one neighbor with $f(w)\geq2$. The weight of a double Roman dominating function $f$ is the sum $f(V)=\sum\nolimits_{v\in V}f(v)$. The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by $\gamma_{\rm dR}(G)$. In this paper, we establish a new upper bound on the double Roman domination number of graphs. We prove that every connected graph $G$ with minimum degree at least two and $G\neq C_5$ satisfies the inequality $\gamma_{\rm dR}(G)\leq\lfloor\frac{13}{11}n\rfloor$. One open question posed by R. A. Beeler et al. has been settled.