On Metric Dimension of Some families of Graph

Abstract

For a connected graph G the distance d(u;v) between two vertices u;v 2V(G) is the length of the shortest path between them. A vertex w of a graph G is said to resolve two vertices u and v of G if d(w;u) 6= d(w;v). Let W = fw1;w2; ::::;wkg be an ordered set of vertices of G and let v be a vertex of G. The representation of a vertex v with respect to W denoted by r(vjW) is the k-tuple (d(v;w1);d(v;w2); :::;d(v;wk)). If distinct vertices of G have distinct representations with respect toW, thenW is called a resolving set for G. The metric dimension of G denoted by dim(G), is the minimum cardinality of a resolving set of G. Graph structure can be used to study the various concepts of Navigation in space. A work place can be denoted as vertex in the graph, and edges denote the connections between the places. The problem of minimum machines (or Robots) to be placed at certain vertices to trace each and every vertex exactly once is a classical one. This problem can be solved by using networks where places are interconnected in which, the navigating agent moves from one vertex to another in the network. The places or vertices of a network where we place the machines (robots) are called landmarks. The minimum number of machines required to locate each and every vertex of the network is termed the metric dimension and the set of all minimum possible number of landmarks constitute metric basis. In this thesis, the metric dimension of some well known families of graphs has been investigated. It is shown that the families of graphs obtained from the path graph by the power, middle and total graph operation have a constant metric dimension. We compute the metric dimension of some rotationally symmetric families of graphs and show that only 2 or 3 vertices appropriately chosen suffice to resolve all the vertices of these graphs. In this thesis, we also compute the metric dimension of some families of convex polytopes with pendant edges. It is shown that the metric dimension of these families of graphs is constant and is independent of the order of these graphs. The metric dimension of the splitting graphs of two families of graph has been computed. We prove that the metric dimension of these graphs is unbounded and depends on the order of the corresponding graph.