Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model

Authors:	Ping-Ying Tsai Jung-Sheng Fu Gen-Huey Chen

Affiliation:	1. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC;2. Department of Computer Science and Information Engineering, Hwa Hsia Institute of Technology, Taipei, Taiwan, ROC;3. Department of Electronic Engineering, National United University, Miaoli, Taiwan, 36003, ROC

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 $n$ -dimensional pancake graph can tolerate up to 2n−7 $2 n - 7$ edge faults, while retaining a fault-free Hamiltonian cycle, where n≥4 $n \geq 4$ . Previously, at most n−3 $n - 3$ edge faults can be tolerated for the same problem, if the edge faults may occur anywhere without imposing any constraint.

Keywords:	Cayley graph Conditional fault model Fault tolerance Hamiltonian cycle Pancake graph
本文献已被 ScienceDirect 等数据库收录！