Proof of the squashed cube conjecture |
| |
Authors: | Peter M. Winkler |
| |
Affiliation: | 1. Dept. of Mathematics and Computer Science, Emory University, 30322, Atlanta, Georgia, USA
|
| |
Abstract: | We prove a conjecture of R. L. Graham and H. O. Pollak to the effect that every connected graph onn vertices has a distance-preserving embedding in “squashed cube” of dimensionn?1. This means that to each vertex of the graph a string ofn?1 symbols from the alphabet {0, 1, *} can be assigned in such a way that the length of the shortest path between two vertices is equal to the Hamming distance between the corresponding strings, with * being regarded as at distance zero from either 1 or 0. Our labelling thus provides an efficient addressing scheme for the loop-switching communications system proposed by J. R. Pierce. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|