• DocumentCode
    1370186
  • 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
  • Volume
    40
  • Issue
    1
  • fYear
    1991
  • fDate
    1/1/1991 12:00:00 AM
  • Firstpage
    88
  • Lastpage
    93
  • 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;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.67323
  • Filename
    67323
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1370186