## Abstract

A t-spanner of a graph G=(V,E), is a sub-graph S_{G}=(V,E′), such that E′⊆E and for every edge {u,v}∈E, there is a path from u to v in S_{G} of length at most t. A minimum-edge t-spanner of a graph G, S_{G}′, is the t-spanner of G with the fewest edges. For general graphs and for t=2, the problem of determining for a given integer s, whether |E(S_{G}′)|≤s is NP-Complete (Peleg and Schaffer, J. Graph Theory 13(1) (1989) 99-116). Peleg and Ullman (SIAM J. Comput. 18(4) (1989) 740-747), give a method for constructing a 3-spanner of the n-vertex Hypercube with fewer than 7n edges. In this paper we give an improved construction giving a 3-spanner of the n-vertex Hypercube with fewer than 4n edges and we present a lower bound of 3n/2-o(1) on the size of the optimal Hypercube 3-spanner.

Original language | English |
---|---|

Pages (from-to) | 289-295 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 103 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 15 Jul 2000 |

Externally published | Yes |