TY - JOUR
ID - 13865
TI - On trees with equal Roman domination and outer-independent Roman domination numbers
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Sheikholeslami, Seyed Mahmoud
AU - Nazari-Moghaddam, Sakineh
AD - Azarbaijan Shahid Madani University
Y1 - 2019
PY - 2019
VL - 4
IS - 2
SP - 185
EP - 199
KW - Roman domination
KW - outer-independent Roman domination
KW - tree
DO - 10.22049/cco.2019.26319.1095
N2 - 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)$.
UR - http://comb-opt.azaruniv.ac.ir/article_13865.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13865_778d0f97a1447e3fa6dcc653002a9d16.pdf
ER -