RESOLVABILITY PARAMETERS IN GRAPHS

An area of research in graph theory, in which a distance-based parameter, called a resolving set, is used to distinguish all the vertices in a connected graph G, is a hot area of research from the past few decades. The concept of a resolving set "a set of vertices of G with the property that the list of distances from any vertex of G to those in the set uniquely distinguishes (identi?es) that vertex", was introduced in mid 1970's by Slater [64] and, independently, by Harary and Melter [31]. Inspired by the work done by many researchers of this area and motivated by the multiple applications of resolving set in many areas such as robot navigation, chemical industry, network discovery and veri?cation, coin weighing problems and strategies for mastermind game, we contribute to the literature in this area by investigating resolving sets in some well-known families of graphs and by studying some new interesting resolving and distance-based parameters. The brief details of our contribution to this area are as follows: We study metric dimension of two families of regular graphs, the circulant graphs Xn,3 and the generalized Petersen graphs P(2m,m?1), and discover that these families of graphs belong to the family of regular graphs with constant metric dimension (metric dimension of a graph which is independent of the choice of the number of vertices of the graph). 2-size metric dimension, which is the cardinality of a minimum resolving set of a graph such that the subgraph induced by it is of size two, is also investigated. Further, we characterize all the connected graphs of order n having 2-size metric dimension n, n?1 and give some realizable results.\ud Fault-tolerant metric dimension of graphs with its generalization "fault-tolerant partition dimension" and their relationship has also been studied. Moreover, we classify all the connected graphs such that the di?erence between their metric dimension and fault-tolerant metric dimension is one. We also characterize all the connected graphs of order n having fault-tolerant partition dimension n and n?1. We study a partition of the vertex set of a graph in which each of its partite set is a resolving set for that graph, and we call it a locatic partition. We give some realizable results and characterize all the connected graphs of order n having locatic partition of maximum cardinality n, n?1 and n?2. We investigate the resolving polynomial of a graph, which is a good representative of the resolving structure of the graph. Also, we characterize all the connected graphs having two resolving roots. Further, the resolving share in graphs, which tells the exact participation of each vertex of the graph in resolving all the pairs of the vertices of that graph, has also been studied. With the help of resolving share, we de?ne and study a distance-based topological index. We propose two integer linear programming formulations: one for fault-tolerant metric dimension problem and second one for local metric dimension problem. We also compute local metric dimension and strong metric dimension of two families of convex polytopes Sn and Un