Authors: N. Jafari Rad, H. Rahbani Title: Bounds on the locating Roman dominating number in trees Source: Discussiones Mathematicae Graph Theory Received 07.01.2016, Revised 21.09.2016, Accepted 21.09.2016, doi: 10.7151/dmgt.1989 | |
Abstract: A Roman dominating function (or just RDF) on a graph G =(V, E) is a function f: V -> {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. The weight of an RDF f is the value f(V(G))=∑_{u ∈V(G)}f(u). An RDF f can be represented as f=(V_{0},V_{1},V_{2}), where V_{i}={v∈V:f(v)=i} for i=0,1,2. An RDF f=(V_{0},V_{1},V_{2}) is called a locating Roman dominating function (or just LRDF) if N(u)∩ V_{2}≠ N(v)∩ V_{2} for any pair u,v of distinct vertices of V_{0}. The locating Roman domination number γ_{R}^{L}(G) is the minimum weight of an LRDF of G. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds. | |
Keywords: Roman domination number, locating domination number, locating Roman domination number, tree | |
Links: |