• DocumentCode
    3485784
  • Title

    On some topological properties of hypercube, incomplete hypercube and supercube

  • Author

    Sen, Arunabha ; Sengupta, Abhijit ; Bandyopadhyay, Subir

  • Author_Institution
    Dept. of Comput. Sci., Arizona State Univ., Tempe, AZ, USA
  • fYear
    1993
  • fDate
    13-16 Apr 1993
  • Firstpage
    636
  • Lastpage
    642
  • Abstract
    Hamiltonian properties of hypercube, incomplete hypercube and supercube are examined. It is known that in a nonfaulty hypercube there are at least n! Hamiltonian cycles. The authors extend this result showing that the lower bound is at least 2n-3n! They show that with at most n-2 faulty links a faulty hypercube has at least 2(n-2)! Hamiltonian cycles. They establish that an incomplete hypercube with odd (even) number of nodes has (n-2)! Hamiltonian paths (cycles). They show that a supercube has at least (n-1)! Hamiltonian cycles and when the number of nodes is 2n-1+2n-2, then the number of Hamiltonian cycles is at least as high as 2(n-1)!
  • Keywords
    graph theory; hypercube networks; Hamiltonian properties; hypercube; incomplete hypercube; nonfaulty hypercube; supercube; topological properties; Computer science; Hamming distance; Hypercubes; Multiprocessor interconnection networks;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1993., Proceedings of Seventh International
  • Conference_Location
    Newport, CA
  • Print_ISBN
    0-8186-3442-1
  • Type

    conf

  • DOI
    10.1109/IPPS.1993.262806
  • Filename
    262806