A Study on Optimal Resolving Set of Graphs and Applications

Abstract

Recently metric dimension and fault-tolerant metric dimension has become a burning newlinetopic of research. Distances play a major role in determining metric dimension newlineand fault-tolerant metric dimension of any arbitrary graph G and it is this distance newlinethat is used to distinguish all the vertices of the graph. If we consider a simple, newlinefinite, and connected graph G = (V (G),E(G)), where V (G) and E(G) represent newlinethe vertex set and the edge set, respectively. The distance between two distinct newlinevertices say u and v is denoted by dG(u, v) or without ambiguity d(u, v). A set newlineW = {w1,w2, . . . ,wk} on which the ordering (w1,w2, . . . ,wk) has been established newlineis referred to as the ordered set of vertices. A vertex y resolves two distinct vertices newlineu and v if d(u, y) and#824;= d(v, y). The code of a vertex u with respect to an ordered set newlineW = {w1,w2, . . . ,wk} is denoted by code(u|W) and is defined by newlinecode(u|W) = (d(u,w1), d(u,w2), . . . , d(u,wk)). newlineIf for every pair of arbitrary vertices u and v in V (G) there is a vertex x and#8712; W newlinesuch that d(x, u) and#824;= d(x, v), then the set W is said to be a resolving set in G. The newlineminimum cardinality (the number of elements in the set) of the resolving set of G newlineis referred to as the metric dimension of G and it is denoted by and#946;(G). The problem newlineof uniquely determining the location of an intruder in a network was the principal newlinemotivation for introducing the concept of metric dimension in graphs, where the newlinemetric generators were called locating sets. newlineA robot navigating in space has been localized by a signaling device, designed newlinebased on graph theoretic concepts. In a set of landmarks with minimum cardinality, newlinethese signaling devices are placed on each element. This means that if one of newlinethese signaling devices isn t working properly, then the robot s position can t be newlinedetermined i.e., if there is a glitch in one of the censors then the whole system newlineis going to collapse and it will be impossible for us to deal with the intruder at newlinethat instant of time. Additional signalling devices would be required