Breaking Symmetry in Graphs by Resolving Sets

Abstract

Let $\dim (G)$ and $D(G)$ respectively denote the metric dimension and the distinguishing number of a graph $G$. It is proved that $D(G)\le \dim (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 $\dim (G)=m$. Using the bound $D(G)\le \dim (G)+1$, graphs with $D(G)=n(G)-2$ are classified.