| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Hamiltonian Path Embedding and Pancyclicity on the Möbius Cube with Faulty Nodes and Faulty Edges
July 2006 (vol. 55 no. 7)
pp. 854-863
A graph G=(V,E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V| in G. Let F_{v} and F_{e} be the sets of faulty nodes and faulty edges of an n{\hbox{-}}{\rm dimensional} Möbius cube MQ_{n}, respectively, and let F=F_{v}\cup F_{e}. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to |V-F_{v}|. In this paper, we show that MQ_{n}-F contains a fault-free Hamiltonian path when |F|\leq n-1 and n\geq 1. We also show that MQ_{n}-F is pancyclic when |F|\leq n-2 and n\geq 2. Since MQ_{n} is regular of degree n, both results are optimal in the worst case.
[1] “Interconnection Networks,” Discrete Applied Math., J.C. Bermond, ed., vols. 37+38, 1992.
[2] P. Cull and S.M. Larson, “The Möbius Cubes,” IEEE Trans. Computers, vol. 44, no. 5, pp. 647-659, May 1995.
[3] J. Fan, “Diagnosability of the Möbius Cubes,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 923-928, Sept. 1998.
[4] J. Fan, “Hamiltonian-Connectivity and Cycle-Embedding of the Möbius Cubes,” Information Processing Letters, vol. 82, pp. 113-117, 2002.
[5] J.-S. Fu and G.-H. Chen, “Hamiltonicity of the Hierarchical Cubic Network,” Theory of Computing Systems, vol. 35, pp. 59-79, 2002.
[6] J.-S. Fu, “Fault-Tolerant Cycle Embedding in the Hypercube,” Parallel Computing, vol. 29, pp. 821-832, 2003.
[7] F. Harary, Graph Theory. Addison-Wesley, 1972.
[8] S.Y. Hsieh and C.H. Chen, “Pancyclicity on Möbius Cubes with Maximal Edge Faults,” Parallel Computing, vol. 30, pp. 407-421, 2004.
[9] D.F. Hsu, “Interconnection Networks and Algorithms,” Networks, vol. 23, no. 4, 1993.
[10] W. Huang, Y. Chuang, J.J.M. Tan, and L. Hsu, “Fault-Free Hamiltonian Cycles in Faulty Möbius Cubes,” Computación y Systemas, vol. 4, no. 2, pp. 106-114, 2000.
[11] W.T. Huang, W.K. Chen, and C.H. Chen, “Pancyclicity of Möbius Cubes,” Proc. Ninth Int'l Conf. Parallel and Distributed Systems (ICPADS '02), pp. 591-596, 2002.
[12] A. Kanevsky and C. Feng, “On the Embedding of Cycles in Pancake Graphs,” Parallel Computing, vol. 21, pp. 923-936, 1995.
[13] H.C. Keh and J.C. Lin, “On Fault-Tolerant Embedding of Hamiltonian Cycles, Linear Arrays and Rings in a Flexible Hypercube,” Parallel Computing, vol. 26, pp. 769-781, 2000.
[14] H. Sarbazi-Azad, M. Ould-Khaoua, and L.M. Mackenzie, “Algorithmic Construction of Hamiltonian in Pyramids,” Information Processing Letters, vol. 80, no. 2, pp. 75-79, 2001.
[15] Y.C. Tseng, S.H. Chang, and J.P. Sheu, “Fault-Tolerant Ring Embedding in Star Graphs with Both Link and Node Failures,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185-1195, Dec. 1997.
[16] G. Tel, Topics in Distributed Algorithms. Cambridge Int'l Series on Parallel Computation, Cambridge Univ. Press, 1991.
Index Terms:
Graph-theoretic interconnection networks, Möbius cubes, fault-tolerant embedding, pancyclicity, Hamiltonian.
Citation:
Sun-Yuan Hsieh, Nai-Wen Chang, "Hamiltonian Path Embedding and Pancyclicity on the Möbius Cube with Faulty Nodes and Faulty Edges," IEEE Transactions on Computers, vol. 55, no. 7, pp. 854-863, July 2006, doi:10.1109/TC.2006.104
