Faul-Free Hamiltonian Cycle in Faulty MÖbius Cubes

WEN-TZENG HUANG , YEN-CHU CHUANG , J. M. TAN JIMMY, LIH-HSING HSU

Resumen


AN N- DIMENSIONAL MOBIUS CUBE, MQ N, IS CREATED BY REARRANGING SOME OF THE CONNECTIONS OF THE HYPERCUBE, QN CULL95 FAN 98. IN THIS PAPER, WE DEMOSTRATE THAT MQN IS (N-3)-HAMILTONIAN CONNECTED AND (N-2)-HAMILTONIAN. IN OTHER WORDS, WE PROVE THAT THERE EXISTS A HAMILTONIAN PATH BETWEEN ANY PAIR OF VERTICES IN A FAULTY MQN WITH N-3 FOULTS, WE ALSO SHOW THAT A RING OF LENGTH 2N-FV CAN BE EMBEDDED IN A FAULTY MQN WITH FV FAULTY MQN WITH N-3 FAULTS. WE ALSO SHOW THAT A RING OR LENGTH 2N-FV CAN BE EMBEDDED IN FAULTY MQN WITH FV FAULTY NODES AND FE FAULTY EDGES, WHERE FV+FE_3 THAT IS, THE FAULTY MQN REMAINS HAMILTONIAN WITH N-2 FAULTS. A RECENT RESULT HAS SHOWN THAT A RING OF LENGTH 2N-2F V CAN BE EMBEDDED IN A FAULTY HYPERCUBE, IF FV+FE<_N-1AND N_<4, WITH A FEW ADDITIONAL CONTRAINTS (SENGUPTA 98). OUR RESULTS, IN COMPARISON TO THE HYPERCUBE, SHOW THAT LONGER RINGS CAN BE EMBEDDED IN MQN WITHOUT ADDITIONAL CONSTRAINTS.

Palabras clave


;MOIBUS CUBE; FAULT TOLERANT; HAMILTONIAN; HAMILTONIAN CONNECTED

Texto completo:

pdf


Contacto:
Oscar Zavala