On k‐detour subgraphs of hypercubes

A spanning subgraph Gof a graph His a k‐detour subgraphof Hif for each pair of vertices $x,y \in V(H)$, the distance, ${\rm dist}_G(x,y)$, between xand yin Gexceeds that in Hby 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