We consider the fault-tolerant capabilities of networks of processors whose underlying topology is that of the k-ary n-cube $Q_n^k$, where $k\geq 3$ and $n\geq 2$. In particular, given a copy of $Q_n^k$ where some of the interprocessor links may be faulty but where every processoris incident with at least two healthy links, we show that if the number of faults is at most 4n-5, then $Q_n^k$ still contains a Hamiltonian circuit, but that there are situations where the number of faults is 4n-4 (and every processor is incident with at least two healthy links) and no Hamiltonian circuit exists. We also remark that given a faulty $Q_n^k$, the problem of deciding whether there exists a Hamiltonian circuit is NP-complete.

We investigate the existence of cycles, meshes and tori in a k-ary n-cube Q/sub n//sup k/ in which a limited number of nodes and links are faulty. Our main result is that in a k-ary n-cube Q/sub n//sup k/ in which there are v faulty nodes /spl lambda/faulty links where v+/spl lambda//spl les/n, there is a cycle of length at least k/sup n/-vw, where w=1 if k is odd and w=2 if k is even (throughout k/spl ges/3 and n/spl ges/2). We extend this result so as to prove the existence of large meshes and tori in such a faulty k-ary n-cube.

In this paper, we consider various topological properties of a k-ary n-cube (Q/sub n//sup k/) using Lee distance. We feel that Lee distance is a natural metric for defining and studying a Q/sub n//sup k/. After defining a Q/sub n//sup k/ graph using Lee distance, we show how to find all disjoint paths between any two nodes. Given a sequence of radix k numbers, a function mapping the sequence to a Gray code sequence is presented, and this function 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/sub n//sup k/ is considered. Using a k-ary Gray code, we show the embedding of a k(n/sub 1/)/spl times/k(n/sub 2/)/spl times/.../spl times/k(n/sub m/)-dimensional mesh into a Q/sub n//sup k/ where n=/spl Sigma//sub i=l//sup m/n/sub i/. Then using a single digit, 4-ary reflective Gray code, we demonstrate embedding a Q/sub n/ into Q/sub [n/2]//sup 4/. We look at how Lee distance may be applied to the problem of resource placement in a Q/sub n//sup k/ by using a Lee distance error-correcting code. Although the results in this paper are only preliminary, Lee distance error-correcting codes have not been applied previously to this problem. Finally, we consider how Lee distance can be applied to message routing and single-node broadcasting in a Q/sub n//sup k/. In this section we present two single-node broadcasting algorithms that are optimal when single-port and multi-port I/O is used.>