FAULT-TOLERANT EMBEDDING OF COMPLETE BINARY-TREES IN HYPERCUBES

This paper is concerned with the following graphtheoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an n-cube, will an (n - 1)-tree still exists as a subgraph? While the general problem of determining whether a k-tree, k < n, still exists when an arbitrary number of nodes/links are removed from the n-cube is found to be NP-complete, we do find that when no more than n - 1 - [log, n] nodes/links are removed, an (n - 1)-tree is guaranteed to exist. In fact, as a corollary of this, we find that if no more than n - 3 nodes/links are removed from an (n - 1)-subcube of the n-cube, an (n - 1)-tree is also guaranteed to exist.