Small Label Classes in 2-Distinguishing Labelings

Abstract

A graph G is said to be 2-distinguishable if there is a labeling of the vertices with two labels so 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 and denote it by ρ(G). This paper shows that for n ≥ 5, ⌈log₂ n ⌉ + 1 ≤ ρ(Q_n) ≤ 2⌈log₂n⌉ − 1, where Q_n is the hypercube of dimension n.