Bounded Degree Spanners of the Hypercube

In this short note we study two questions about the existence of subgraphs of the hypercube $Q_n$ with certain properties. The first question, due to Erd\H{o}s–Hamburger–Pippert–Weakley, asks whether there exists a bounded degree subgraph of $Q_n$ which has diameter $n$. We answer this question by giving an explicit construction of such a subgraph with maximum degree at most 120. The second problem concerns properties of $k$-additive spanners of the hypercube, that is, subgraphs of $Q_n$ in which the distance between any two vertices is at most $k$ larger than in $Q_n$. Denoting by ${\mathrm{\Delta }}_{k,\mathrm{\infty }}(n)$ the minimum possible maximum degree of a $k$-additive spanner of $Q_n$, Arizumi–Hamburger–Kostochka showed that $$\frac{n}{\ln n}{e}^{-4k}\le {\mathrm{\Delta }}_{2k,\mathrm{\infty }}(n)\le 20\frac{n}{\ln n}\ln \ln n\mathrm{.}$$ We improve their upper bound by showing that $${\mathrm{\Delta }}_{2k,\mathrm{\infty }}(n)\le {10}^{4k}\frac{n}{\ln n}{\ln }^{(k+1)}n,$$where the last term denotes a $k+1$-fold iterated logarithm.