GRAPHS WITH MINIMUM METRIC DIMENSION
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) =...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/38494 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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. |
|---|