Distinguishing graphs of maximum valence 3

Abstract

The distinguishing number $D(G)$ of a graph $G$ is the smallest number of colors that is needed to color $G$ such that the only color preserving automorphism is the identity. We give a complete classification for all connected graphs $G$ of maximum valence $△(G)=3$ and distinguishing number $D(G)=3$. As one of the consequences we get that all infinite connected graphs with $△(G)=3$ are 2-distinguishable.

18 pages, 9 figures