The twisted N-cube with application to multiprocessing

Abstract

It is shown that by exchanging any two independent edges in any shortest cycle of the n-cube (n>or=3), its diameter decreases by one unit. This leads to the definition of a new class of n-regular graphs, denoted TQ/sub n/, with 2/sup n/ vertices and diameter n-1, which has the (n-1)-cube as subgraph. Other properties of TQ/sub n/ such as connectivity and the lengths of the disjoints paths are also investigated. Moreover, it is shown that the complete binary tree on 2/sup n/-1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQ/sub n/. How these results can be used to enhance hypercube multiprocessors is discussed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>