On k‐detour subgraphs of hypercubes |
| |
Authors: | Nana Arizumi Peter Hamburger Alexandr Kostochka |
| |
Institution: | 1. University of Illinois, Urbana Illinois 61801;2. Department of Mathematics, Western Kentucky University, Bowling Green, Kentucky 42101;3. Department of Mathematics, University of Illinois, Urbana, Illinois, 61801;4. Institute of Mathematics, Novosibirsk 630090, Russia |
| |
Abstract: | A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , 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, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008 |
| |
Keywords: | hypercube additive spanner k‐detour |
|
|