Bounded Degree Spanners of the Hypercube

Abstract

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 Erdos-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 Delta(k,infinity)(n) the minimum possible maximum degree of a k-additive spanner of Q(n), Arizumi-Hamburger-Kostochka showed that n/ln n e(-4k) <= Delta(2k,infinity)(n) <= 20 n/ln n ln ln n. We improve their upper bound by showing that Delta(2k,infinity)(n) <= 10(4k) n/ln n ln((k+1)) n, where the last term denotes a k + 1-fold iterated logarithm.