The Cost of \(2\)-Distinguishing Selected Kneser Graphs and Hypercubes

Debra L.Boutin1
1Hamilton College Clinton, NY 13323

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. The minimum size of a label class in such a labeling of \( G \) is called the cost of 2-distinguishing and is denoted by \( \rho(G) \). This paper shows that \( \rho(K_{2^m-1}:2^{m-1}-1) = m+1 \) — the only result so far on the cost of 2-distinguishing Kneser graphs. The result for Kneser graphs is adapted to show that \( \rho(Q_{2^m-2}) = \rho(Q_{2^m-1}) = \rho(Q_{2^m}) = m+2 \) — a significant improvement on previously known bounds for the cost of 2-distinguishing hypercubes.