A spanning subgraph G of a graph H is a k-detour subgraph of H if for each pair of vertices $x,y \in V(H)$, the distance, ${\rm dist}_G(x,y)$, between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k-detour subgraphs of the n-dimensional cube, $Q^n$, with few edges or with moderate maximum degree. Let $\Delta(k,n)$ denote the minimum possible maximum degree of a k-detour subgraph of $Q^n$. The main result is that for every $k\geq 2$ and $n \geq 21$ $$e^{-2k} {{n} \over {\ln n}} \le \Delta(k,n) \le 20 {n{\ln {\ln n}} \over {\ln n}}.$$ On the other hand, for each fixed even $k \geq 4$ and large n, there exists a k-detour subgraph of $Q^n$ with average degree at most $2 + 2^{4-k/2}+o(1)$. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008
['Nana Arizumi', 'Peter Hamburger', 'Alexandr V. Kostochka']
On k-detour subgraphs of hypercubes