Small label classes in 2-distinguishing labelings
Debra Boutin · Ars Mathematica Contemporanea · 2008
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 2 n ⌉ + 1 ≤ ρ ( Q n ) ≤ 2⌈log 2 n ⌉ − 1, where Q n is the hypercube of dimension n .