Distinguishing trees in linear time (Q426889)

Summary: A graph is said to be \(d\)-distinguishable if there exists a \(d\)-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph \(G\) is the smallest number \(d\) for which \(G\) is \(d\)-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known \(O(n\log n)\) time algorithm.