The Metric Dimension of Unicyclic Graphs



For an ordered set $W=\{w_1, w_2, \cdots, w_k\}$ of vertices and a vertex $v$ in a graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)$ = ($d(v, w_1),$ $ d(v, w_2), $ $ \cdots,$ $ d(v, w_k)$), where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations. A resolving set containing a minimum number of vertices is called a basis for $G$ and the number of vertices in a basis is the (metric) dimension $\dim G$. A connected graph is unicyclic if it contains exactly one cycle. For a unicyclic graph $G$, tight bounds for $\dim G$ are derived. It is shown that all numbers between these bounds are attainable as the dimension of some unicyclic graph.