Locating Roman Domination in Graphs

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)) Sigma(u is an element of V(G)) f (u). An RDF f can be represented as f = (V-0, V-1, V-2), where V-i = {v is an element of 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) boolean AND V-2 not equal N(v) boolean AND V-2 for any pair u, v of distinct vertices of V-0. The locating Roman domination number gamma(L)(R)(G) is the minimum weight of an LRDF of G. In this paper, we initiate the study of the locating Roman domination number in graphs. We show that the decision problem for the locating Roman domination problem is NP-complete for bipartite graphs and chordal graphs. We relate the locating Roman domination number to the Roman domination number and also locating domination number, and present several bounds and characterizations for the locating Roman domination number of a graph.