The Cost of 2-Distinguishing Hypercubes

Abstract

A graph $G$ is said to be {\it $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, over all 2-distinguishing labelings, is called the {\it cost of $2$-distinguishing}, denoted by $\rho (G)$. For $n\ge 4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $\rho (Q_n)$ have been elusive, with only bounds and partial results previously known. This paper settles the question. The main result can be summarized as: for $n\ge 4$, $\rho (Q_n)\in \{1+\lceil {\log }_{2}n\rceil ,2+\lceil {\log }_{2}n\rceil \}$. Exact values are be found using a recursive relationship involving a new parameter ${\nu }_m$, the smallest integer for which $\rho (Q_{{\nu }_m})=m$. The main result is\begin{gather*} 4\leq n \leq 12\Longrightarrow ρ(Q_n)=5, \text{ and } 5\leq m \leq 11 \Longrightarrow ν_m=4; \\ \text{ for } m\geq 6, ρ(Q_n) = m \iff 2^{m-2} - ν_{m-1} + 1 \leq n \leq 2^{m-1}-ν_m; \\ \text{ for } n\geq 5, ν_m = n \iff 2^{n-1} - ρ(Q_{n-1}) + 1\leq m \leq 2^{n}-ρ(Q_n).\end{gather*}