Fault-free Hamiltonian cycles in faulty arrangement graphs

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 期刊論文 > Item 987654321/29150

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/29150

題名:	Fault-free Hamiltonian cycles in faulty arrangement graphs
作者:	Hsieh,SY;Chen,GH;Ho,CW
貢獻者:	資訊工程研究所
關鍵詞:	HYPERCUBES;NETWORKS;DEBRUIJN;MESHES;RINGS;TREES
日期:	1999
上傳時間:	2010-06-29 20:14:55 (UTC+8)
出版者:	中央大學
摘要:	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).
關聯:	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
顯示於類別:	[資訊工程研究所] 期刊論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	475	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....