A characterization of trees with equal Roman $\{2\}$-domination and Roman domination numbers

Abstract

Given a graph $G=(V,E)$ and a vertex $v \in V$, by $N(v)$ we represent the open neighbourhood of $v$. Let $f:V\rightarrow \{0,1,2\}$ be a function on $G$. The weight of $f$ is $\omega(f)=\sum_{v\in V}f(v)$ and let $V_i=\{v\in V \colon f(v)=i\}$, for $i=0,1,2$. The function $f$ is said to be \begin{itemize} \item a Roman $\{2\}$-dominating function, if for every vertex $v\in V_0$, $\sum_{u\in N(v)}f(u)\geq 2$. The Roman $\{2\}$-domination number, denoted by $\gamma_{\{R2\}}(G)$, is the minimum weight among all Roman $\{2\}$-dominating functions on $G$; \item a Roman dominating function, if for every vertex $v\in V_0$ there exists $u\in N(v)\cap V_2$. The Roman domination number, denoted by $\gamma_R(G)$, is the minimum weight among all Roman dominating functions on $G$. \end{itemize} It is known that for any graph $G$, $\gamma_{\{R2\}}(G)\leq \gamma_R(G)$. In this paper, we characterize the trees $T$ that satisfy the equality above.

Keywords

• Roman $\{2\}$-domination; $2$-rainbow domination; Roman domination; tree