Geodesic
Distinguishability of locally finite trees
The electronic journal of combinatorics, Tome 14 (2007)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
Mark E. Watkins; Xiangqian Zhou. Distinguishability of locally finite trees. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/947

Cité par Sources :