| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Fault Hamiltonicity and Fault Hamiltonian Connectivity of the Arrangement Graphs
January 2004 (vol. 53 no. 1)
pp. 39-53
Abstract—The arrangement graph An,k is a generalization of the star graph. There are some results concerning fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graph. However, these results are restricted in some particular cases and, thus, are less completed. In this paper, we improve these results and obtain a stronger and simpler statement. Let n-k \ge 2 and F \subseteq V(An,k) \cup E(An,k). We prove that An,k - F is Hamiltonian if |F| \le k(n-k) -2 and An,k - F is Hamiltonian connected if |F| \le k(n-k) -3. These results are optimal.
[1] 39 S.B. Akers, D. Harel, and B. Krishnamurthy, The Star Graph: An Attractive Alternative to then-Cube Proc. Int'l Conf. Parallel Processing, pp. 216-223, 1986.[2] S.B. Akers and B. Krishnamurthy, “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. Computers, vol. 38, no. 4, pp. 555-566, Apr. 1989.[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. New York: North Holland, 1980.[4] M.Y. Chan and S.J. Lee, On the Existence of Hamiltonian Circuits in Faulty Hypercubes SIAM J. Discrete Math., vol. 4, no. 4, pp. 511-527, Nov. 1991.[5] W.K. Chiang and R.J. Chen, On the Arrangement Graph Information Processing Letters, vol. 66, pp. 215-219, 1998.[6] K. Day and A. Tripathi, Arrangement Graphs: A Class of Generalized Star Graphs Information Processing Letters, vol. 42, no. 5, pp. 235-241, 1992.[7] K. Day and A. Tripathi,“Embedding of cycles in arrangement graphs,” IEEE Trans. Computers, vol. 42, no. 8, pp. 1,002-1,006, Aug. 1993.[8] S.Y. Hsieh, G.H. Chen, and C.W. Ho, “Fault-Free Hamiltonian Cycles in Faulty Arrangement Graphs,” IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 3, pp. 223-237, 1999.[9] S.Y. Hsieh, G.H. Chen, and C.W. Ho, Longest Fault-Free Paths in Star Graphs with Edge Faults IEEE Trans. Computers, vol. 50, no. 9, pp. 960-971, Sept. 2001.[10] W.T. Huang, J.M. Tan, C.N. Hung, and L.H. Hsu, Fault-Tolerant Hamiltonicity of Twisted Cubes J. Parallel and Distributed Computing, accepted, 2001.[11] S. Latifi, S. Zheng, and N. Bagherzadeh, "Optimal Ring Embedding in Hypercubes with Faulty Links," Proc. Fault-Tolerant Computing Symp., pp. 178-184, 1992.[12] R.S. Lo and G.H. Chen, Embedding Hamiltonian Paths in Faulty Arrangement Graphs with the Backtracking Method IEEE Trans. Parrallel and Distributed Systems, vol. 12, no. 2, pp. 209-221, Feb. 2001.[13] O. Ore, Hamiltonian Connected Graph J. Math. Pures Applications, vol. 42, pp. 121-127, 1963.[14] R.A. Rowley and B. Bose, “Fault-Tolerant Ring Embedding in deBruijn Networks,” IEEE Trans. Computers, vol. 42, no. 12, pp. 1480-1486, Dec. 1993.[15] Y. Saad and M. Schultz, "Topological Properties of Hypercubes," IEEE Trans. Computers, vol. 37, no. 7, pp. 867-872, July 1988.[16] Y.C. Tseng, S.H. Chang, and J.P. Sheu, “Fault-Tolerant Ring Embedding in a Star Graph with Both Link and Node Failures,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185-1195, Dec. 1997.
Index Terms:
Hamiltonian cycle, Hamiltonian connected, fault tolerance, arrangement graph.
Citation:
Hong-Chun Hsu, Tseng-Kuei Li, Jimmy J.M. Tan, Lih-Hsing Hsu, "Fault Hamiltonicity and Fault Hamiltonian Connectivity of the Arrangement Graphs," IEEE Transactions on Computers, vol. 53, no. 1, pp. 39-53, Jan. 2004, doi:10.1109/TC.2004.1255789
