On 2-detour subgraphs of the hypercube

Research output: Contribution to journalArticlepeer-review


A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), dH(x. y) ≤ dG(x, y) + 2. We prove a conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Qn has at least c log2 n · 2n edges.

Original languageEnglish (US)
Pages (from-to)265-272
Number of pages8
JournalGraphs and Combinatorics
Issue number4
StatePublished - Sep 2008


  • Additive spanner
  • Detour subgraph
  • Extremal subgraph
  • Graph
  • Hypercube

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this