A study on metric dimension and dominant metric dimension of graphs

Abstract

In modeling real-world problems, graphs have emerged as a useful, practical, and effective tool. Utilizing them more frequently has made them standard practice in transportation, computer science, engineering, and science. Monitoring a network for an intruder by deploying sensing devices in certain places of the network is the main aim of the concept of finding the metric dimension of a graph.Slater introduced the concept of resolving set of a connected graph in the name of locating set when working with loran and sonar in the 19th century. Harary and Melter described the same concept in terms of resolving set. However, the problem of finding the metric dimension of general graphs is NP-complete. Many of the researchers studied this concept extensively by describing graphs with constant metric dimensions, computing bounds, and determining the metric dimension of various graphs. This motivates the present study on the metric dimension of graphs.Let G = (V, E) be a connected graph. By an ordered set of vertices, we mean a subset W = {w1, w2, ..., wk} g V (G) on which the ordering (w1, w2, ..., wk) has been imposed. For an ordered subset W = {w1, w2, .. , wk} of vertices and a vertex v in a connected graph G, the ordered k-vector r(vIW) = (d(v,w1), d(v,w2), ..., d(v,wk)) is called the representation of v with respect to W. The set W is called a resolving set of G if r (ul W) = r(v I W) implies that u = v for all u, v E V (G). A minimum resolving set is a metric basis of G and its cardinality is the metric dimension of G, denoted as dim(G). newline