On k-detour subgraphs of hypercubes

✍ Scribed by Nana Arizumi; Peter Hamburger; Alexandr Kostochka

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 156 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20281

✦ Synopsis

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 additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, $Q^n$, with few edges or with moderate maximum degree. Let $\Delta(k,n)$ denote the minimum possible maximum degree of a k‐detour subgraph of $Q^n$. The main result is that for every $k\geq 2$ and $n \geq 21$

On the other hand, for each fixed even $k \geq 4$ and large n, there exists a k‐detour subgraph of $Q^n$ with average degree at most $2 + 2^{4-k/2}+o(1)$. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008