Outer independent Roman domination number of trees

Document Type : Original paper


1 Sirjan University of Technology, Sirjan 78137, Iran

2 LAMDA-RO Laboratory, Department of Mathematics University of Blida B.P. 270, Blida, Algeria


‎A Roman dominating function (RDF) on a graph G=(V,E) is a function 
f : V → {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 ΥoiR (G) is the minimum weight‎
‎of an OIRDF on $G$‎. ‎In this paper‎, ‎we show that if T is a tree of order n ≥ 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‎.


Main Subjects