Infinite Graphs with Finite 2-Distinguishing Cost

Abstract

A graph $G$ is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of $G$ the cost of 2-distinguishing $G$.

We show that the connected, locally finite, infinite graphs with finite 2-distinguishing cost are exactly the graphs with countable automorphism group. Further we show that in such graphs the cost is less than three times the size of a smallest determining set. We also another, sharper bound on the 2-distinguishing cost, in particular for graphs of linear growth.