Hypercube subgraphs with minimal detours
P�l Erd�s, Peter Hamburger, Raymond E. Pippert, William D. Weakley · Journal of Graph Theory · 1996
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.