On k-detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k-detour subgraph of H if for each pair of vertices x, y ∈ V(H), the distance, distc(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ⁿ, with few edges or with moderate maximum degree. Let Δ(k, n) denote the minimum possible maximum degree of a k-detour subgraph of Qⁿ. The main result is that for every k > 2 and n > 21, e^-2k n/ln ≤Δ(k, n) ≤20 n ln ln n/in n. On the other hand, for each fixed even k ≥ 4 and large n, there exists a k-detour subgraph of Qⁿ with average degree at most 2 + 2 ^4-k/2 + o(1).