Multipacking in Hypercubes

Abstract

For an undirected graph $G$, a dominating broadcast on $G$ is a function $f:V(G)\to \mathbb{N}$ such that for any vertex $u\in V(G)$, there exists a vertex $v\in V(G)$ with $f(v)⩾1$ and $d(u,v)⩽f(v)$. The cost of $f$ is ${\sum }_{v\in V}f(v)$. The minimum cost over all the dominating broadcasts on $G$ is defined as the broadcast domination number ${\hat{I}}_b^3(G)$ of $G$. A multipacking in $G$ is a subset $M\subseteq V(G)$ such that, for every vertex $v\in V(G)$ and every positive integer $r$, the number of vertices in $M$ within distance $r$ of $v$ is at most $r$. The multipacking number of $G$, denoted $\mathrm{mp}(G)$, is the maximum cardinality of a multipacking in $G$. These two optimisation problems are duals of each other, and it easily follows that $\mathrm{mp}(G)⩽{\hat{I}}_b^3(G)$. It is known that ${\hat{I}}_b^3(G)⩽2\mathrm{mp}(G)+3$ and conjectured that ${\hat{I}}_b^3(G)⩽2\mathrm{mp}(G)$. In this paper, we show that for the $n$-dimensional hypercube $Q_n$ $$\lfloor \frac{n}{2}\rfloor ⩽\mathrm{mp}(Q_n)⩽\frac{n}{2}+6\sqrt{2n}.$$ Since ${\hat{I}}_b^3(Q_n)=n-1$ for all $n⩾3$, this verifies the above conjecture on hypercubes and, more interestingly, gives a sequence of connected graphs for which the ratio $\frac{{\hat{I}}_b^3(G)}{\mathrm{mp}(G)}$ approaches $2$, a search for which was initiated by Beaudou, Brewster and Foucaud in 2018. It follows that, for connected graphs $G$ $$\underset{\mathrm{mp}(G)\to \infty }{\mathrm{limsup}}\left\{\frac{{\hat{I}}_b^3(G)}{\mathrm{mp}(G)}\right\}=2.$$ The lower bound on $\mathrm{mp}(Q_n)$ is established by a recursive construction, and the upper bound is established using a classic result from discrepancy theory.