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

Ying-Sian Wu, Jun-Yo Chen

Published 2022-03-31Version 1

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)$ when $n\geq9$ and $n\ne2^{k},2^{k}-1 $ for any $k\in\mathbb{N} $. In this article, we present a new method using congruence properties given by Laurent Habsieger(1997) and improved the lower bounds on $\gamma(Q_n)$ when $n $ is a multiple of 6.