Metric Dimens Ion And Domination Related Parameters Of Graphs

The distance d(x,y)between two vertices x and y in a connected graph G is the length of a shortest path x,y between those two vertices.Let R an ordered set R={r1,r2,...,rk}of vertices in G,and x?G,the representation of x with respect to R is the k-vector,Cr(x)=(d(x,r1),d(x,r2),...,d(x,rx)).The set R is resolving set of G if distinct vertices in G have distinct representation.A resolving set incorporating the least number of vertices is a basis for G.The metric dimension is usually denoted by ?(G)is the number of vertices in a basis for G.A resolving set R for the graph G is fault-tolerant if for each x?R,R\{x}is a resolving set for G.A fault-tolerant resolving set is a resolving set in which the removal of an arbitrary vertex maintains the resolvability.We denote the fault-tolerant metric dimension of graph G with ?'(G).The fault-tolerant metric dimension ?'(G)is the minimum cardi-nality of fault-tolerant resolving set.A fault-tolerant resolving set of order ?'(G)is called fault-tolerant metric basis.The concept of metric dimension was introduced in 1953 but initially failed to attract the intentions of many researchers,however two decades later it was investigated to ob-serve distance among the vertices for a graph G.Since then it has been used regularly in different fields such as chemistry,graph theory,robotics and many other known disciplines.Depending upon the diverse number of situations which can arise in determining the problem of differentiating the vertices of a graph,several concepts of metric dimension have been investigated over the past few decades.Later Hernando,independently put forward the concept of fault tolerant metric dimension,which endure the eradication of any arbitrary vertex and perpetuate the resolvability status of that underying graph.When the vertices in a resolving set are considered as the locations for some lonar,sonar stations,in such a scenario we can propose that location of any such a vertex in a graph is determined by the distance of vertices from the site of those stations.From this point of view,a fault-tolerant resolving set still determine the resolving set even neglecting any of a station at a uniquely determined location of a vertex in the resolving set.Fault-tolerant resolving set improves the relevance of classical resolving sets in a graph.In addition to that fault-tolerant met-ric dimension have superiority in terms of applicative point of view over the metric dimension.In Chapter 1,we gave background and some definitions which are useful to understand the concept in a more better way and along with it,we presented important theorems and lemmas which are used in the subsequent chapters.In Chapter 2,we studied the fault-tolerant metric dimension problem for convex polytopes A convex polytope is a polytope which is also a convex set of points in the n-dimensional Euclidean space Rn.By preserving the same adjacency relation between vertices of a convex polytope,its graph is constructed.The metric dimension problem has been extensively studied for convex poly topes and other families of graphs.By using a relation between resolving sets and fault-tolerant resolving sets of graphs,it was proved that certain infinite families of convex polytopes are the families of graphs with constant fault-tolerant metric dimension.In Chapter 3,we considered fault-tolerant resolving sets in graphs.We characterized n-vertex graphs with a fault-tolerant metric dimension n,n-1 and 2 which are the lower and upper extremal cases.Furthermore,in the first part,a method was presented to locate fault-tolerant resolving sets by using classical resolving sets in graphs.The second part applied the proposed method to three infinite families of regular graphs and locates certain fault-tolerant resolving sets.By accumulating the obtained results with some known results in the literature,we presented certain lower and upper bounds on the fault-tolerant metric dimension of these families of graphs.As a byproduct,it was shown that these families of graphs preserve a constant fault-tolerant resolvability structure.In Chapter 4,we discussed potential applications of metric dimension and fault-tolerant metric dimension in telecommunication,robot navigation and geographical routing proto-cols,and other fields.The computational complexity of these problems is known to be NP-complete.In this chapter,we studied the fault-tolerant metric dimension of various inter-connection networks.By using the resolving sets in these networks,we located fault-tolerant resolving sets in them.As a result,certain lower and upper bounds on the fault-tolerant metric dimension of those networks were obtained.In Chapter 5,a different approach was considered as we studied the problem of binary locating-dominating number for the graphs of convex polytopes which are rotationally sym-metric.Graphs of convex polytopes emerge from geometric structures of convex polytopes by preserving the adjacency-incidence relation vertices.In this chapter,we proposed an integer linear programming(ILP)formulation for the binary locating-dominating problem of graphs.We determined the exact values of the binary locating-dominating number for two infinite families of convex polytopes.Moreover,certain upper bounds were determined for other three infinite families of convex polytopes.By using the proposed ILP formulation,we showed tightness in the obtained upper bounds.In Chapter 6,we presented the conclusion of this thesis and we gave few open problems which were raised during our study.Those open problems can be tackled in future projects.