Title :
The twisted N-cube with application to multiprocessing
Author :
Esfahanian, Abdol Hossein ; Ni, Lionel M. ; Sagan, Bruce E.
Author_Institution :
Michigan State Univ., East Lansing, MI, USA
fDate :
1/1/1991 12:00:00 AM
Abstract :
It is shown that by exchanging any two independent edges in any shortest cycle of the n-cube (n⩾3), its diameter decreases by one unit. This leads to the definition of a new class of n-regular graphs, denoted TQn, with 2n vertices and diameter n-1, which has the (n-1)-cube as subgraph. Other properties of TQn such as connectivity and the lengths of the disjoints paths are also investigated. Moreover, it is shown that the complete binary tree on 2n-1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQn. How these results can be used to enhance hypercube multiprocessors is discussed
Keywords :
graph theory; hypercube networks; trees (mathematics); complete binary tree; connectivity; disjoints paths; hypercube multiprocessors; multiprocessing; n-regular graphs; subgraph; twisted N-cube; Binary trees; Graph theory; Hypercubes; Message passing; Multiprocessor interconnection networks; Network topology; Routing; Terminology; Tree graphs; Zinc;
Journal_Title :
Computers, IEEE Transactions on
