# On Computing the Distinguishing Numbers of Trees and Forests

### Abstract

Let $G$ be a graph. A vertex labeling of $G$ is *distinguishing* if the only label-preserving automorphism of $G$ is the identity map. The *distinguishing number* of $G$, $D(G)$, is the minimum number of labels needed so that $G$ has a distinguishing labeling. In this paper, we present $O(n \log n)$-time algorithms that compute the distinguishing numbers of trees and forests. Unlike most of the previous work in this area, our algorithm relies on the combinatorial properties of trees rather than their automorphism groups to compute for their distinguishing numbers.