Distinguishing Graphs of Maximum Valence 3

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

Abstract

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.

Published
2019-11-22
Article Number
P4.36