Hypercube subgraphs with local detours

A minimal detour subgraph of the n ‐dimensional cube is a spanning subgraph G of Q n having the property that, for vertices x , y of Q n , distances are related by d G ( x , y ) ≤ $d_{Q_{n}}(x, y)$ + 2. For a spanning subgraph G of Q n to be a local detour subgraph , we require only that the above inequality be satisfied whenever x and y are adjacent in Q n . Let f ( n ) (respectively, f l ( n )) denote the minimum number of edges in any minimal detour (respectively, local detour) subgraph of Q n (cf. Erdös et al. [1]). In this article, we find the asymptotics of f l ( n ) by showing that 3 · 2 n (1 − ( n −1/2 )) < f l ( n ) < 3 · 2 n (1 + o (1)). We also show that f ( n ) > 3.00001 · 2 n ( for n > n 0 ), thus eventually f l ( n ) < f ( n ), answering a question of [1] in the negative. We find the order of magnitude of F l ( n ), the minimum possible maximum degree in a local detour subgraph of Q n : $\sqrt{2n + 0.25} - 0.5 \leq F_{l}(n) \leq 1.5\sqrt{2n} - 1.$ © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 101–111, 1999