Distinguishing graphs of maximum valence 3 (Q2278113)

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