Hypercube subgraphs with minimal detours

Define a minimal detour subgraph of the n-dimensional cube to be a spanning subgraph G of Qn having the property that for vertices x, y of Qn, distances are related by dG(x, y) ≤ dQn(x, y) + 2. Let f(n) be the minimum number of edges of such a subgraph of Qn. After preliminary work on distances in subgraphs of product graphs, we show that The subgraphs we construct to establish this bound have the property that the longest distances are the same as in Qn, and thus the diameter does not increase. We establish a lower bound for f(n), show that vertices of high degree must be distributed throughout a minimal detour subgraph of Qn, and end with conjectures and questions. © 1996 John Wiley & Sons, Inc.