On Minimum Metric Dimension of Architectures

Bharati Rajan

Loyola College, Chennai

Abstract

A collision-free path for a movable object among obstacles is an interesting problem in the field of robotics. A robot is a mechanical device which is made to move in space with obstructions around. It has neither the concept of direction nor that of visibility. But it is assumed that it can sense the distances to a set of landmarks. Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position in space is uniquely determined.

Let $M=\{v_{1},$ $v_{2}$ $...$ $v_{n}\}$ be an ordered set of vertices in a graph $G$. Then $(d(u,v_{1}),$ $d(u,v_{2})$ $...$ $d(u,v_{n}))$ is called the $M$-coordinates of a vertex $u$ of $G$. The set $M$ is called a metric basis if the vertices of $G$ have distinct $M$-coordinates. A minimum metric basis is a metric basis $M$ with minimum cardinality. If $M$ is a metric basis then it is clear that for each pair of vertices $u$ and $v$ of $%