## Abstract

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_{Qn} (x, y)+2. Fora 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. Erdos et al. [1]). In this article, we find the asymptotics of f_{l}(n) by showing that 3 · 2^{n}(1 - O(n-^{1/2})) < f_{l}(n) < 3 · 2^{n}(1 + 0(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}: √2n + 0.25 - 0.5 ≤ F_{l}(n) ≤ 1.5√2n - 1.

Original language | English (US) |
---|---|

Pages (from-to) | 101-111 |

Number of pages | 11 |

Journal | Journal of Graph Theory |

Volume | 30 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1999 |

Externally published | Yes |

## Keywords

- Hypercube
- Local detour
- Minimal detour

## ASJC Scopus subject areas

- Geometry and Topology