Ring embedding in faulty pancake graphs

被引：35
作者：
Hung, CN
Hsu, HC
Liang, KY
Hsu, LH
机构：
[1] Da Yet Univ, Dept Comp Sci & Informat Engn, Changhua 51505, Taiwan
[2] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu 300, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 05期
关键词：
fault tolerance; Hamiltonian; Hamiltonian connected; pancake graphs;
D O I：
10.1016/S0020-0190(02)00510-0
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph P-n. Assume that F subset of or equal to V(P-n) boolean OR E(P-n). For n greater than or equal to 4, we prove that P-n - F is hamiltonian if \F\ less than or equal to (n - 3) and P-n - F is hamiltonian connected if \F\ less than or equal to (n - 4). Moreover, all the bounds are optimal. (C) 2003 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：271 / 275
页数：5
相关论文
共 10 条
[1]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[2]  
Bondy J.A., 1980, Graph Theory with Applications
[3]   Embedding complete binary trees into star and pancake graphs [J].
Bouabdallah, A ;
Heydemann, MC ;
Opatrny, J ;
Sotteau, D .
THEORY OF COMPUTING SYSTEMS, 1998, 31 (03) :279-305
[4]  
FANG WC, 2000, INFORM SCI, P191
[5]   FAULT-TOLERANT ROUTING IN THE STAR AND PANCAKE INTERCONNECTION NETWORKS [J].
GARGANO, L ;
VACCARO, U ;
VOZELLA, A .
INFORMATION PROCESSING LETTERS, 1993, 45 (06) :315-320
[6]   BOUNDS FOR SORTING BY PREFIX REVERSAL [J].
GATES, WH ;
PAPADIMITRIOU, CH .
DISCRETE MATHEMATICS, 1979, 27 (01) :47-57
[7]   On the diameter of the pancake network [J].
Heydari, MH ;
Sudborough, IH .
JOURNAL OF ALGORITHMS, 1997, 25 (01) :67-94
[8]  
HUANG WT, IN PRESS J PARALLEL
[9]  
HUANG WT, IN PRESS IEICE T FUN
[10]   ON THE EMBEDDING OF CYCLES IN PANCAKE GRAPHS [J].
KANEVSKY, A ;
FENG, C .
PARALLEL COMPUTING, 1995, 21 (06) :923-936
1