標題: | Fault Hamiltonicity and fault Hamiltonian connectivity of the (n, k)-star graphs |
作者: | Hsu, HC Hsieh, YL Tan, JJM Hsu, LH 資訊工程學系 Department of Computer Science |
關鍵字: | Hamiltonian cycle;Hamiltonian connected;(n, k)-star graph |
公開日期: | 1-十二月-2003 |
摘要: | In this paper, we consider the fault Hamiltonicity, and the fault Hamiltonian connectivity of the (n, k)-star graph S-n,S-k. Assume that F subset of V(S-n,S-k) boolean OR E(S-n,S-k). For n - k greater than or equal to 2, we prove that S-n,S-k - F is Hamiltonian if F less than or equal to n - 3 and S-n,S-k - F is Hamiltonian connected if F less than or equal to n - 4. For n - k = 1, S-n,S-n-1 is isomorphic to the n-star graph S-n which is known to be Hamiltonian if and only if n > 2 and Hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight. (C) 2003 Wiley Periodicals, Inc. |
URI: | http://dx.doi.org/10.1002/net.10096 http://hdl.handle.net/11536/27348 |
ISSN: | 0028-3045 |
DOI: | 10.1002/net.10096 |
期刊: | NETWORKS |
Volume: | 42 |
Issue: | 4 |
起始頁: | 189 |
結束頁: | 201 |
顯示於類別: | 期刊論文 |