## Abstract

A spanning subgraph G of a graph H is a k-detour subgraph of H if for each pair of vertices x, y ∈ V(H), the distance, distc(x, y), between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k-detour subgraphs of the n-dimensional cube, Q^{n}, with few edges or with moderate maximum degree. Let Δ(k, n) denote the minimum possible maximum degree of a k-detour subgraph of Q^{n}. The main result is that for every k > 2 and n > 21, e^{-2k} n/ln ≤Δ(k, n) ≤20 n ln ln n/in n. On the other hand, for each fixed even k ≥ 4 and large n, there exists a k-detour subgraph of Q^{n} with average degree at most 2 + 2 ^{4-k/2} + o(1).

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

Pages (from-to) | 55-64 |

Number of pages | 10 |

Journal | Journal of Graph Theory |

Volume | 57 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2008 |

## Keywords

- Additive spanner
- Hypercube
- k-detour

## ASJC Scopus subject areas

- Geometry and Topology
- Discrete Mathematics and Combinatorics