Paper detail

The Cost of 2-Distinguishing Hypercubes

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 $ρ(G)$. For $n\geq 4$ the hypercubes $Q_n$ are 2-distinguishable, but the values for $ρ(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\geq 4$, $ρ(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 $ν_m$, the smallest integer for which $ρ(Q_{ν_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*}