Distinguishability of locally finite trees (Q874003)

Summary: The distinguishing number \(\Delta(X)\) of a graph \(X\) is the least positive integer \(n\) for which there exists a function \(f:V(X)\rightarrow \{0,1,2,\dots,n-1\}\) such that no nonidentity element of \(\text{Aut}(X)\) fixes (setwise) every inverse image \(f^{-1}(k)\), \(k \in \{0,1,2,\dots,n-1\}\). All infinite, locally finite trees without pendant vertices are shown to be 2-distinguishable. A proof is indicated that extends 2-distinguishability to locally countable trees without pendant vertices. It is shown that every infinite, locally finite tree \(T\) with finite distinguishing number contains a finite subtree \(J\) such that \(\Delta(J)=\Delta(T)\). Analogous results are obtained for the distinguishing chromatic number, namely the least positive integer \(n\) such that the function \(f\) is also a proper vertex-coloring.