✦ LIBER ✦

Hypercube subgraphs with local detours

✍ Scribed by Hamburger, Peter; Kostochka, Alexandr V.; Sidorenko, Alexander

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 131 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199902)30:2<101::aid-jgt4>3.0.co;2-9

No coin nor oath required. For personal study only.

✦ Synopsis

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. For a 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 * Dedicated to the memory of Paul Erd ős

📜 SIMILAR VOLUMES

Hypercube subgraphs with minimal detours

✍ Erd�s, P�l; Hamburger, Peter; Pippert, Raymond E.; Weakley, William D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 546 KB

Define a minimal detour subgraph of the n-dimensional cube to be a spanning subgraph G of Qn having the property that for vertices 2, y of Qn, distances are related by dG(z, y) 5 dQ,(z,y) + 2. Let f(n) be the minimum number of edges of such a subgraph of Qn. After preliminary work on distances in s

On k-detour subgraphs of hypercubes

✍ Nana Arizumi; Peter Hamburger; Alexandr Kostochka 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

## Abstract A spanning subgraph __G__ of a graph __H__ is a __k__‐__detour subgraph__ of __H__ if for each pair of vertices $x,y \in V(H)$, the distance, ${\rm dist}\_G(x,y)$, between __x__ and __y__ in __G__ exceeds that in __H__ by at most __k__. Such subgraphs sometimes also are called __additiv