Locating Roman Domination in Graphs
Abstract
A Roman dominating function (or just RDF) on a graph G = (V,E) is a function/: 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/is the value f(V(G)) = £uV(C) f(u)-RDF/can be represented as/= (Vo, Vj, V2), where V{ = {v V : F(v) = i} for i = 0,1,2. An RDF/= (Vo, Vi, V2) is called a locating Roman dominating function (or just LRDF) if N(u) nV2 N(v) n V2 for any pair u,v of distinct vertices of Vq. The locating Roman domination number 7r(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. © 2019 Utilitas Mathematica Publishing Inc.. All rights reserved.
