Fault-tolerant ring embedding in faulty arrangement graphs
Sun‐Yuan Hsieh, Gen-Huey Chen · 2002
The arrangement graph A/sub n,k/, which is a generalization of the star graph (n-t=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 proven 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)-1, 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 3/|/spl les/k.