Geodesic
Distinguishability of locally finite trees
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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.
DOI : 10.37236/947
Classification : 05C05, 05C12
Mots-clés : distinguishing number, chromatic number 
Mark E. Watkins; Xiangqian Zhou. Distinguishability of locally finite trees. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/947
@article{10_37236_947,
     author = {Mark E. Watkins and Xiangqian Zhou},
     title = {Distinguishability of locally finite trees},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/947},
     zbl = {1112.05026},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/947/}
}
TY  - JOUR
AU  - Mark E. Watkins
AU  - Xiangqian Zhou
TI  - Distinguishability of locally finite trees
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/947/
DO  - 10.37236/947
ID  - 10_37236_947
ER  - 
%0 Journal Article
%A Mark E. Watkins
%A Xiangqian Zhou
%T Distinguishability of locally finite trees
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/947/
%R 10.37236/947
%F 10_37236_947

Cité par Sources :