AIMS Mathematics (Feb 2021)

A note on the bounds of Roman domination numbers

  • Zepeng Li

DOI
https://doi.org/10.3934/math.2021234
Journal volume & issue
Vol. 6, no. 4
pp. 3940 – 3946

Abstract

Read online

Let $G$ be a graph and $f: V(G) \rightarrow \{0,1,2\}$ be a mapping. $f$ is said to be a Roman dominating function of $G$ if every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. The weight $w(f)$ of a Roman dominating function $f$ is the value $w(f) = \sum_{u \in V(G)}f(u)$, and the minimum weight of a Roman dominating function is the Roman domination number $\gamma_R(G)$. $f$ is said to be a Roman $\{2\}$-dominating function of $G$ if $\sum_{v\in N(u)}f(v)\geq 2$ for every vertex $u$ with $f(u)= 0$, where $N(u)$ is the set of neighbors of $u$ in $G$. The weight of a Roman \{2\}-dominating function $f$ is the sum $\sum_{v\in V}f(v)$ and the minimum weight of a Roman \{2\}-dominating function is the Roman \{2\}-domination number $\gamma_{\{R2\}}(G)$. Chellali et al. (2016) proved that $\gamma_{R}(G)\geq\frac{\Delta+1}{\Delta}\gamma(G)$ for every nontrivial connected graph $G$ with maximum degree $\Delta$. In this paper, we generalize this result on nontrivial connected graph $G$ with maximum degree $\Delta$ and minimum degree $\delta$. We prove that $\gamma_{R}(G)\geq\frac{\Delta+2\delta}{\Delta+\delta}\gamma(G)$, which also implies that $\frac{3}{2}\gamma(G)\leq\gamma_{R}(G)\leq 2\gamma(G)$ for any nontrivial regular graph. Moreover, we prove that $\gamma_{R}(G)\leq2\gamma_{\{R2\}}(G)-1$ for every graph $G$ and there exists a graph $I_k$ such that $\gamma_{\{R2\}}(I_k)=k$ and $\gamma_{R}(I_k)=2k-1$ for any integer $k\geq2$.

Keywords