A note on the double Roman domination number of graphs

Chen, Xue-Gang

Czechoslovak Mathematical Journal, Tome 70 (2020) no. 1, pp. 205-212

Abstract (VO)

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)\geq 2$. 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.

Détail

DOI : 10.21136/CMJ.2019.0212-18

Classification : 05C35, 05C69
Keywords: double Roman domination number; domination number; minimum degree