Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model
The conditional fault model imposes a constraint on the fault distribution. For example, the most commonly imposed constraint for edge faults is that each vertex is incident with two or more non-faulty edges. In this paper, subject to this constraint, we show that an n-dimensional pancake graph can tolerate up to 2n - 7 edge faults, while retaining a fault-free Hamiltonian cycle, where n >= 4. Previously, at most n - 3 edge faults can be tolerated for the same problem, if the edge faults may occur anywhere without imposing any constraint. (C) 2008 Elsevier B.V. All rights reserved.
pancake graph conditional fault model hamiltonian cycle cayley graph fault tolerance