New Upper Bounds on the Minimal Domination Numbers of High-Dimensional Hypercubes

We briefly review known results on upper bounds for the minimal domination number ${\gamma }_n$ of a hypercube of dimension $n$, then present a new method for constructing dominating sets. Write $n=2^{\widehat{n}}-1+\check{n}$ with $0\le \check{n}<2^{\widehat{n}}$. Our construction applies to all $n$ lying within the expanding wedge $\theta (\widehat{n})\le \check{n}<2^{\widehat{n}}$, where $\theta$ is a specific, easily computable function with the asymptotic property $\theta (a)\sim 2^{a\mathrm{/}2}$. For all $n$ within the smaller wedge $\theta (\widehat{n})\le \check{n}<2^{\widehat{n}-2}$, the resulting upper bound on ${\gamma }_n$ betters those previously known.