HYPERCUBE SUBGRAPHS WITH MINIMAL DETOURS

Define a minimal detour subgraph of the n-dimensional cube to be a spa nning subgraph G of Q(n) having the property that for vertices x, y of Q(n), distances are related by d(G)(x, y) less than or equal to d(Qn) (x, y) + 2. Let f(n) be the minimum number of edges of such a subgrap h of Q(n). After preliminary work on distances in subgraphs of product graphs, we show that f(n)/\E((Qn)\ < c/root n. The subgraphs we const ruct to establish this bound have the property that the longest distan ces are the same as in Q(n), 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 Q(n), and end with conjectures and questions. (C) 1996 John Wiley & Sons, Inc.