The arrangement graph is a generalization of the star graph. Recent work by Hsieh et al. showed that an arrangement graph with faulty vertices contains a longest fault-free cycle. In this paper, we generalize Hsieh et al.'s result by constructing a longest fault-free path between two arbitrary distinct healthy vertices. Moreover, our result can tolerate more faulty vertices than can Hsieh et al.'s result. The situation of simultaneous faulty vertices and faulty edges is also discussed. © 2001 John Wiley & Sons, Inc.

The arrangement graph, denoted by A/sub n,k/, is a generalization of the star graph. A recent work by S.Y. Hsieh et al. (1999) showed that when n-k/spl ges/4 and k=2 or n-k/spl ges/4+[k/2] and k/spl ges/3, A/sub n,k/ with k(n-k)-2 random edge faults, can embed a Hamiltonian cycle. In this paper, we generalize Hsieh et al. work by embedding a Hamiltonian path between arbitrary two distinct vertices of the same A/sub n,k/. To overcome the difficulty arising from random selection of the two end vertices, a new embedding method, based on a backtracking technique, is proposed. Our results can tolerate more edge faults than Hsieh et al. results as k/spl ges/7 and 7/spl les/n-k/spl les/3+[k/2], although embedding a Hamiltonian path between arbitrary two distinct vertices is more difficult than embedding a Hamiltonian cycle.