BIRS Workshop Lecture Videos
On the distinguishing number of locally finite trees Hüning, Svenja
The distinguishing number $D(G)$ of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ such that the only color-preserving automorphism on $G$ is the identity. We are interested in the distinguishing number of locally finite trees. Our work is motivated by the "Infinite Motion Conjecture" given by Tucker in 2011. It says that $D(G) = 2$ if every non-identity automorphism of a given connected, locally finite, infinite graph $G$ moves infinitely many vertices. In this talk, we study the question how many vertices of a tree with bounded valence $k$ can be fixed with $c$ colors. We show that all vertices whose distance to the next leaf is at least $\lceil log_c k \rceil$ can be fixed. This is joint work with W. Imrich, J. Kloas, H. Schreiber and T. Tucker.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International