| 摘要: | The arrangement graph A(n,k), which is a generalization bf the star graph (n - k = 1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously, the arrangement graph has proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even ii it is faulty. Let \F-e\ and \F-v\ denote the numbers of edge faults and vertex faults, respectively. We show that A(n,k) is Hamiltonian when 1) (k = 2 and n - k greater than or equal to 4, or k greater than or equal to 3 and n - k greater than or equal to 4 + inverted right perpendicular k/2 inverted left perpendicular), and \F-e\ less than or equal to k(n - k) - 2, or 2) k greater than or equal to 2, n - k greater than or equal to 2 + inverted right perpendicular k/2 inverted left perpendicular, and \F-e\ less than or equal to k(n - k - 3) - 1, or 3) k greater than or equal to 2, n - k greater than or equal to 3, and \F-e\ less than or equal to k, or 4) n - k greater than or equal to 3 and \F-v\ less than or equal to n - 3, or 5) n - k greater than or equal to 3 and \F-v\ + \F-e\ less than or equal to k. Besides, for A(n,k) with n - k = 2, we construct a cycle of length at least 1) n!/(n-k)! - 2 if \F-e\ less than or equal to k - 1, or 2) n!/(n-k)! - \F-v\ - 2(k -1) if \F-v\ less than or equal to k - 1, or 3) n!/(n-k)! - \F-v\ - 2(k - 1) if \F-e\ + \F-v\ less than or equal to k - 1, where nl/(n-k)l is the number of nodes in A(n,k). |
