Breaking Symmetry in Graphs by Resolving Sets

Let $\mathrm{d}\mathrm{i}\mathrm{m}(G)$ and $D(G)$ respectively denote the metric dimension and the distinguishing number of a graph $G$. It is proved that $D(G)\le \mathrm{d}\mathrm{i}\mathrm{m}(G)+1$ holds for every connected graph $G$. Among trees, exactly paths and stars attain the bound, and among connected unicyclic graphs such graphs are $t$-cycles for $t\in \{3,4,5\}$. It is shown that for any $1\le n<m$, there exists a graph $G$ with $D(G)=n$ and $\mathrm{d}\mathrm{i}\mathrm{m}(G)=m$. Using the bound $D(G)\le \mathrm{d}\mathrm{i}\mathrm{m}(G)+1$, graphs with $D(G)=n(G)-2$ are classified.