標題: | Ring embedding in faulty pancake graphs |
作者: | Hung, CN Hsu, HC Liang, KY Hsu, LH 資訊工程學系 Department of Computer Science |
關鍵字: | fault tolerance;Hamiltonian;Hamiltonian connected;pancake graphs |
公開日期: | 15-六月-2003 |
摘要: | 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. |
URI: | http://dx.doi.org/10.1016/S0020-0190(02)00510-0 http://hdl.handle.net/11536/27789 |
ISSN: | 0020-0190 |
DOI: | 10.1016/S0020-0190(02)00510-0 |
期刊: | INFORMATION PROCESSING LETTERS |
Volume: | 86 |
Issue: | 5 |
起始頁: | 271 |
結束頁: | 275 |
顯示於類別: | 期刊論文 |