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.
@article{10_37236_2285,
author = {Carlos Seara and Antoni Lozano and Merc\`e Mora},
title = {Distinguishing trees in linear time},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2285},
zbl = {1243.05214},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2285/}
}
TY - JOUR
AU - Carlos Seara
AU - Antoni Lozano
AU - Mercè Mora
TI - Distinguishing trees in linear time
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2285/
DO - 10.37236/2285
ID - 10_37236_2285
ER -
%0 Journal Article
%A Carlos Seara
%A Antoni Lozano
%A Mercè Mora
%T Distinguishing trees in linear time
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2285/
%R 10.37236/2285
%F 10_37236_2285
Carlos Seara; Antoni Lozano; Mercè Mora. Distinguishing trees in linear time. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2285
