Distinguishing Graphs of Maximum Valence 3

  • Svenja Hüning
  • Wilfried Imrich
  • Judith Kloas
  • Hannah Schreber
  • Thomas W. Tucker


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.

Article Number