The Metric Dimension of Unicyclic Graphs

Abstract

For an ordered set $W=\{w_1,w_2,\dots ,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),\dots ,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.