On k-detour subgraphs of hypercubes

Nana Arizumi, Peter Hamburger, Alexandr Kostochka

Research output: Contribution to journalArticlepeer-review


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, Qn, with few edges or with moderate maximum degree. Let Δ(k, n) denote the minimum possible maximum degree of a k-detour subgraph of Qn. 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 Qn with average degree at most 2 + 2 4-k/2 + o(1).

Original languageEnglish (US)
Pages (from-to)55-64
Number of pages10
JournalJournal of Graph Theory
Issue number1
StatePublished - Jan 2008


  • Additive spanner
  • Hypercube
  • k-detour

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On k-detour subgraphs of hypercubes'. Together they form a unique fingerprint.

Cite this