Distinguishability of Locally Finite Trees
Open Access
- 3 January 2007
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 14 (1) , R29
Abstract
The distinguishing number $\Delta(X)$ of a graph $X$ is the least positive integer $n$ for which there exists a function $f:V(X)\to\{0,1,2,\cdots,n-1\}$ such that no nonidentity element of $\hbox{Aut}(X)$ fixes (setwise) every inverse image $f^{-1}(k)$, $k\in\{0,1,2,\cdots,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.
Keywords
This publication has 5 references indexed in Scilit:
- Distinguishing labellings of group action on vector spaces and graphsJournal of Algebra, 2006
- On Computing the Distinguishing Numbers of Trees and ForestsThe Electronic Journal of Combinatorics, 2006
- Symmetry Breaking in GraphsThe Electronic Journal of Combinatorics, 1996
- Automorphisms and endomorphisms of infinite locally finite graphsAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1973
- ber unendliche Wege in GraphenMathematische Annalen, 1964