Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21286220211201Outer independent Roman domination number of trees2732861416210.22049/cco.2021.27072.1191ENNasrinDehgardiSirjan University of Technology, Sirjan 78137, IranMChellaliLAMDA-RO Laboratory, Department of Mathematics
University of Blida
B.P. 270, Blida, AlgeriaJournal Article20201002A Roman dominating function (RDF) on a graph $G=(V,E)$ is a function $f:Vrightarrow {0,1,2}$ such that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. An RDF $f$ is called an outer independent Roman dominating function (OIRDF) if the set of vertices assigned a $0$ under $f$ is an independent set. The weight of an OIRDF is the sum of its function values over all vertices, and the outer independent Roman domination number $gamma _{oiR}(G)$ is the minimum weight of an OIRDF on $G$. In this paper, we show that if $T$ is a tree of order $ngeq 3$ with $s(T)$ support vertices, then $gamma _{oiR}(T)leq min {frac{5n}{6},frac{3n+s(T)}{4}}.$ Moreover, we characterize the tress attaining each bound.http://comb-opt.azaruniv.ac.ir/article_14162_bc649d348f3b3863bd5517b8d106538d.pdf