Fault-free Hamiltonian cycles in faulty arrangement graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29150

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29150

Title:	Fault-free Hamiltonian cycles in faulty arrangement graphs
Authors:	Hsieh,SY;Chen,GH;Ho,CW
Contributors:	資訊工程研究所
Keywords:	HYPERCUBES;NETWORKS;DEBRUIJN;MESHES;RINGS;TREES
Date:	1999
Issue Date:	2010-06-29 20:14:55 (UTC+8)
Publisher:	中央大學
Abstract:	The arrangement graph A(n,k), which is a generalization bf the star graph (n - k = 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 proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even ii it is faulty. Let \F-e\ and \F-v\ denote the numbers of edge faults and vertex faults, respectively. We show that A(n,k) is Hamiltonian when 1) (k = 2 and n - k greater than or equal to 4, or k greater than or equal to 3 and n - k greater than or equal to 4 + inverted right perpendicular k/2 inverted left perpendicular), and \F-e\ less than or equal to k(n - k) - 2, or 2) k greater than or equal to 2, n - k greater than or equal to 2 + inverted right perpendicular k/2 inverted left perpendicular, and \F-e\ less than or equal to k(n - k - 3) - 1, or 3) k greater than or equal to 2, n - k greater than or equal to 3, and \F-e\ less than or equal to k, or 4) n - k greater than or equal to 3 and \F-v\ less than or equal to n - 3, or 5) n - k greater than or equal to 3 and \F-v\ + \F-e\ less than or equal to k. Besides, for A(n,k) with n - k = 2, we construct a cycle of length at least 1) n!/(n-k)! - 2 if \F-e\ less than or equal to k - 1, or 2) n!/(n-k)! - \F-v\ - 2(k -1) if \F-v\ less than or equal to k - 1, or 3) n!/(n-k)! - \F-v\ - 2(k - 1) if \F-e\ + \F-v\ less than or equal to k - 1, where nl/(n-k)l is the number of nodes in A(n,k).
Relation:	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	479	View/Open

社群 sharing

Loading...