GRAPHS WITH MINIMUM METRIC DIMENSION

• Main Author: Salim, Anderson
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/38494
• Institution: Institut Teknologi Bandung

Let G be a connected graph. The distance between two vertices u and v in G, denoted by d(u; v), is the length of the shortest path between u and v in G. If W = fw1;w2; : : : ;wkg is an ordered subset of vertices of G, then the metric representation of u with respect to W is the k-vector r(ujW) = (d(u;w1); d(u;w2); : : : ; d(u;wk)). W is a resolving set of G if r(ujW) 6= r(vjW) for every two distinct vertices u and v in G. The metric dimension of G, denoted by dim(G), is the minimum cardinality of a resolving set of G. Chartrand et.al in one of their article managed to determine the metric dimension of some graphs. They also determined the lower bound of metric dimension of a graph and proved that the metric dimension of trees equals to the lower bound. In this final project, we prove that the metric dimension of a rooted product between a graph and a tree equals to the lower bound. We also prove that the metric dimension of a partial rooted product between a graph and a tree equals to the lower bound with some restrictions.