A characterization of trees with equal Roman 2-domination and Roman domination numbers

Document Type: Original paper

Authors

1 University of Cadiz

2 Universitat Rovira i Virgili

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:Vrightarrow {0,1,2}$ be a function on $G$. The weight of $f$ is $omega(f)=sum_{vin V}f(v)$ and let $V_i={vin 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 $vin V_0$, $sum_{uin 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 $vin V_0$ there exists $uin 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

Main Subjects