solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3596次
Distinguishing locally finite trees. (arXiv:1810.02265v1 [math.CO])
来源于:arXiv
The distinguishing number $D(G)$ of a graph $G$ is the smallest number of
colors that is needed to color the vertices of $G$ such that the only color
preserving automorphism is the identity. For infinite graphs $D(G)$ is bounded
by the supremum of the valences, and for finite graphs by $\Delta(G)+1$, where
$\Delta(G)$ is the maximum valence. Given a finite or infinite tree $T$ of
bounded finite valence $k$ and an integer $c$, where $2 \leq c \leq k$, we are
interested in coloring the vertices of $T$ by $c$ colors, such that every color
preserving automorphism fixes as many vertices as possible. In this sense we
show that there always exists a $c$-coloring for which all vertices whose
distance from the next leaf is at least $\lceil\log_ck\rceil$ are fixed by any
color preserving automorphism, and that one can do much better in many cases. 查看全文>>