Isometric embedding in products of complete graphs |
| |
Authors: | Peter M Winkler |
| |
Institution: | Department of Mathematics and Computer Science, Emory University, Atlanta GA 30322, USA |
| |
Abstract: | An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers of K3. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|