An upper bound on the double Roman domination number (Q5895065): Difference between revisions

From the summary: ``A double Roman dominating function (DRDF) on a graph \(G=(V, E)\) is a function \(f: V\to \{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)\ge 2\). The weight of a DRDF \(f\) is the value \(f(V)=\sum_{u\in V} f(u)\). The double Roman domination number \(\gamma_{\mathrm{dR}}(G)\) of a graph \(G\) is the minimum weight of a DRDF on \(G\). \textit{R. A. Beeler} et al. [Discrete Appl. Math. 211, 23--29 (2016; Zbl 1348.05146)] observed that every connected graph \(G\) having minimum degree at least two satisfies the inequality \(\gamma_{\mathrm{dR}}(G)\le\frac{6n}{5}\).'' In this article, the authors improve this bound to \(\gamma_{\mathrm{dR}}(G)\le\frac{8n}{7}\) for all simple graphs of order \(n\) with minimum degree at least \(2\) except for the cycle of order \(5\) (for which the previous bound is sharp). The new bound is sharp for the cycle of order \(7\).