On trees with equal Roman domination and outer-independent Roman domination numbers

Document Type : Original paper


Azarbaijan Shahid Madani University


A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) to {0, 1, 2}$
satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one
vertex $v$ for which $f(v) = 2$. A Roman dominating function $f$ is called an outer-independent
Roman dominating function (OIRDF) on $G$ if the set ${vin Vmid f(v)=0}$ is independent.
The (outer-independent) Roman domination number $gamma_{R}(G)$ ($gamma_{oiR}(G)$) is the minimum weight
of an RDF (OIRDF) on $G$. Clearly for any graph $G$, $gamma_{R}(G)le gamma_{oiR}(G)$. In this paper,
we provide a constructive characterization of trees $T$ with $gamma_{R}(T)=gamma_{oiR}(T)$.


Main Subjects