LEE DISTANCE AND TOPOLOGICAL PROPERTIES OF K-ARY N-CUBES

In this paper, we consider various topological properties of a k-ary n -cube (Q(n)(k)) using Lee distance. We feel that Lee distance is a nat ural metric for defining and studying a Q(n)(k). After defining a Q(n) (k) graph using Lee distance, we show how to find all disjoint paths b etween any two nodes. Given a sequence of radix k numbers, a function mapping the sequence to a Gray code sequence is presented, and this fu nction is used to generate a Hamiltonian cycle. Embedding the graph of a mesh and the graph of a binary hypercube into the graph of a Q(n)(k ) is considered. Using a k-ary Gray code, we show the embedding of a k (n1) x k(n2) x ... x k(nm)-dimensional mesh into a Q(n)(k) where n = S igma(i=1)(m)n(i). Then using a single digit, 4-ary reflective Gray cod e, we demonstrate embedding a Q(n) into a Q([n/2]) (4). We look at how Lee distance may be applied to the problem of resource placement in a Q(n)(k) by using a Lee distance error-correcting code. Although the r esults in this paper are only preliminary, Lee distance error-correcti ng codes have not been applied previously to this problem. Finally, we consider how Lee distance can be applied to message routing and singl e-node broadcasting in a Q(n)(k). In this section we present two singl e-node broadcasting algorithms that are optimal when single-port and m ulti-port I/O is used.