Bounded degree spanners of the hypercube (Q782941): Difference between revisions

Summary: 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 \textit{P. Erdős} et al. [J. Graph Theory 23, No. 2, 119--128 (1996; Zbl 0857.05027)], 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,\infty}(n)\) the minimum possible maximum degree of a \(k\)-additive spanner of \(Q_n\), \textit{N. Arizumi} et al. [ibid. 57, No. 1, 55--64 (2008; Zbl 1203.05110)] showed that \[\frac{n}{\ln n}e^{-4k}\leq \Delta_{2k,\infty}(n)\leq 20\frac{n}{\ln n}\ln \ln n.\] We improve their upper bound by showing that \[\Delta_{2k,\infty}(n)\leq 10^{4k} \frac{n}{\ln n}\ln^{(k+1)}n,\] where the last term denotes a \(k+1\)-fold iterated logarithm.