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.