Distinguishing Trees in Linear Time

Carlos Seara, Antoni Lozano, Mercè Mora


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.


distinguishing number, trees, forests

Full Text: