The arrangement graph A/sub n,k/, which is a generalization of 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 if it is faulty. Let |F/sub e/| and |F/sub v/| denote the numbers of edge faults and vertex faults, respectively. We show that A/sub n,k/ is Hamiltonian when 1) (k=2 and n-k/spl ges/4, or k/spl ges/3 and n-k/spl ges/4+[k/2]), and |F/sub e/|/spl les/k(n-k)-2, or 2) k/spl ges/2, n-k/spl ges/2+[k/2], and |F/sub e/|/spl les/k(n-k-3)-1, or 3) k/spl ges/2, n-k/spl ges/3, and |F/sub e/|/spl les/k, or 4) n-k/spl ges/3 and |F/sub v/|/spl les-3, or 5) n-k/spl ges/3 and |F/sub v/|+|F/sub e/|/spl les/k. Besides, for A/sub n,k/ with n-k=2, we construct a cycle of length at least 1) [n!/(n-k!)]-2 if |F/sub e/|/spl les/k-1, or 2) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub v/|/spl les/k-1, or 3) [n!/(n-k)!]-|F/sub v/|-2(k-1) if |F/sub e/|+|F/sub v/|/spl les/k-1, where [n!/(n-k)!] is the number of nodes in A/sub n,k/.
展开▼
机译：布置图A / sub n，k /是星形图（n-k = 1）的概括，在调节主要设计参数：节点数，度和直径方面，比星形图具有更大的灵活性。以前，排列图已证明是哈密顿量。在本文中，我们进一步表明，即使有故障，排列图仍保持哈密顿量。令| F / sub e / |和| F / sub v / |分别表示边缘故障和顶点故障的数量。我们证明当1）（k = 2和nk / spl ges / 4，或k / spl ges / 3和nk / spl ges / 4 + [k / 2]）时，A / sub n，k /是哈密顿量，并且| F / sub e / | / spl les / k（nk）-2，或2）k / spl ges / 2，nk / spl ges / 2 + [k / 2]和| F / sub e / | / spl les / k（nk-3）-1或3）k / spl ges / 2，nk / spl ges / 3和| F / sub e / | / spl les / k，或4）nk / spl ges / 3和| F / sub v / | / spl les / n-3，或5）nk / spl ges / 3和| F / sub v / | + | F / sub e / | / spl les / k。此外，对于nk = 2的A / sub n，k /，如果| F / sub e / | / spl les / k-，则构造一个长度至少为1）[n！/（nk！）]-2的循环。 1或2）[n！/（nk）！]-| F / sub v / | -2（k-1），如果| F / sub v / | / spl les / k-1，或3）[n ！/（nk）！]-| F / sub v / | -2（k-1），如果| F / sub e / | + | F / sub v / | / spl les / k-1，则[n！ /（nk）！]是A / sub n，k /中的节点数。
展开▼
