Abstract
A graph G = (V, E) is a non-empty collection of vertices and edges, where V is the vertex set, E the edge set and |V (G)| is the order of a graph. The diameter, D, of a graph is the maximum distance between any two vertices. A set W of vertices is a resolving set if each vertex of G is determined by the distances to all vertices of W. The metric dimension of a graph, denoted by k, is defined as the smallest cardinality of a resolving set in G. Resolving sets and metric dimension have applications in robot navigation, sensor placement in networks, contamination location, as well as pharmaceutical chemistry and pattern recognition with image processing. This work investigates the metric dimension of graphs in terms of order and diameter, for certain graph classes such as interval graphs, unit interval graphs, permutation graphs, outerplanar graphs and trees. New bounds on metric dimension are established for bipartite graphs of given order and diameter.
M.Sc. (Applied Mathematics)