Hypercube subgraphs with local detours

Peter Hamburger, Alexandr V. Kostochka, Alexander Sidorenko

Research output: Contribution to journalArticlepeer-review

Abstract

A minimal detour subgraph of the n-dimensional cube is 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. Fora spanning subgraph G of Qn to be a local detour subgraph, we require only that the above inequality be satisfied whenever x and y are adjacent in Qn. Let f(n) (respectively, fl(n)) denote the minimum number of edges in any minimal detour (respectively, local detour) subgraph of Qn (cf. Erdos et al. [1]). In this article, we find the asymptotics of fl(n) by showing that 3 · 2n(1 - O(n-1/2)) < fl(n) < 3 · 2n(1 + 0(1)). We also show that f(n) > 3.00001 · 2n (for n > n0), thus eventually fl(n) < f(n), answering a question of [1] in the negative. We find the order of magnitude of fl(n), the minimum possible maximum degree in a local detour subgraph of Qn: √2n + 0.25 - 0.5 ≤ Fl(n) ≤ 1.5√2n - 1.

Original languageEnglish (US)
Pages (from-to)101-111
Number of pages11
JournalJournal of Graph Theory
Volume30
Issue number2
DOIs
StatePublished - Feb 1999
Externally publishedYes

Keywords

  • Hypercube
  • Local detour
  • Minimal detour

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Hypercube subgraphs with local detours'. Together they form a unique fingerprint.

Cite this