Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model
Resource
Theoretical Computer Science 409 (3): 450-460
Journal
Theoretical Computer Science
Pages
450-460
Date Issued
2008
Date
2008
Author(s)
Abstract
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 2 n - 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. © 2008 Elsevier B.V. All rights reserved.
Subjects
Cayley graph; Conditional fault model; Fault tolerance; Hamiltonian cycle; Pancake graph
Other Subjects
Graph theory; Hamiltonians; Meats; Quality assurance; Reliability; Cayley graph; Conditional fault model; Edge faults; Fault distributions; Fault models; Fault-tolerant; Faulty edges; Hamiltonian cycle; Hamiltonian cycles; Hamiltonicity; Pancake graph; Pancake graphs; Fault tolerance
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
49.pdf
Size
1.45 MB
Format
Adobe PDF
Checksum
(MD5):f209cb14139bcddeee2d1460026636ec