On the embedding of a class of regular graphs in a faulty hypercube

In a hypercube of high dimension, the interconnection is quite complex and thus links are likely to fail. In this paper, a general, systematic solution is proposed for the embedding of a group of regular graphs in an injured hypercube with faulty links. These graphs include rings, linear paths, binomial trees, binary trees, meshes, tori, products of the above graphs, and many others. Unlike many existing algorithms which are capable of embedding only one type of graphs, our algorithm embeds the above graphs in a unified way, all centered around a notion called edge matrix. (C) 1996 Academic Press, Inc.