Improved Lower Bounds on the Domination Number of Hypercubes and Binary Codes with Covering Radius One

Abstract

A dominating set on an $n$-dimensional hypercube is equivalent to a binary covering code of length $n$ and covering radius 1. It is still an open problem to determine the domination number $\gamma (Q_n)$ for $n\ge 10$ and $n\ne 2^k,2^k-1$ ($k\in \mathbb{N}$). When $n$ is a multiple of 6, the best known lower bound is $\gamma (Q_n)\ge \frac{2^n}{n}$, given by Van Wee (1988). In this article, we present a new method using congruence properties due to Laurent Habsieger (1997) and obtain an improved lower bound $\gamma (Q_n)\ge \frac{(n-2)2^n}{n^2-2n-2}$ when $n$ is a multiple of 6.

14 pages, 1 figure