RESULTS ON RESOLVABILITY AND METRIC DIMENSION IN GRAPHS

A. T. Shahida and M. S. Sunitha

  DOI:
  https://doi.org/10.37418/amsj.9.4.43

Full Text

For an ordered subset $W=\{w_{1}, w_{2},…,w_{k}\}$ of $V(G)$ and a vertex $v\in V$, the metric representation of $v$ with respect to $W$ is a $k$-vector, which is defined as $r(v/W)=(d(v,w_{1}), d(v,w_{2}),…,d(v,w_{k}))$, where $d(u, v)$ represents the distance between the vertices $u$ and $v$. The set $W$ is called a resolving set for $G$ if $r(u/W)=r(v/W)$ implies that $u= v$ for all $u,v \in V(G)$. In this paper, the total number of resolving sets for a path graph $P_{n}$ is obtained. Established that total number of resolving sets in a simple connected graph $G$ is greater than or equal to $2^{n-k}-1$, where $k = dim(G)$. Discussed about $K_{m,n}$ $ m\geq 2, n > m-2$, does not admit independent basis. Established that every basis for hypercube $Q_{3}$ is either independent or connected and every basis of Petersen graph $(P)$ is independent. Characterized the graph $G$ with $dim(G) = 2$, which does not admit an independent basis.


Keywords:
Metric dimension, Metric basis, Resolving set.