✦ LIBER ✦

Hypercube subgraphs with minimal detours

✍ Scribed by Erd�s, P�l; Hamburger, Peter; Pippert, Raymond E.; Weakley, William D.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 546 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199610)23:2<119::aid-jgt3>3.0.co;2-w

No coin nor oath required. For personal study only.

✦ Synopsis

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 subgraphs of product graphs, we show that f(n)/lE(Qnl < 46.

The subgraphs we construct to establish this bound have the property that the longest distances are the same as in Qn, and thus the diameter does not increase.

We establish a lower bound for f(n), show that vertices of high degree must be distributed throughout a minimal detour subgraph of Qn, and end with conjectures and questions.

📜 SIMILAR VOLUMES

Hypercube subgraphs with local detours

✍ Hamburger, Peter; Kostochka, Alexandr V.; Sidorenko, Alexander 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

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 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