Mutually independent Hamiltonian cycles in dual-cubes
檔案
- 000282225700006.pdf (545.8 KB, Adobe PDF)
日期
2010-11-01
類型
系所
期刊名稱
JOURNAL OF SUPERCOMPUTING
卷期與頁次
第 54 卷第 2 期,頁 239–251
ISSN
0920-8542
語言
英文
摘要
The hypercube family Q(n) is one of the most well-known interconnection networks in parallel computers. With Q(n) , dual-cube networks, denoted by DC(n) , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC(n)'s are shown to be superior to Q(n)'s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC(n) contains n+1 mutually independent Hamiltonian cycles for n >= 2. More specifically, let upsilon(i) is an element of V(DC (n) ) for 0 <= i <= |V(DC(n))|-1 and let (upsilon(0,) upsilon(1,.....,) upsilon broken vertical bar v(DC(n))broken vertical bar-1, upsilon(0)) be a Hamiltonian cycle of DC(n) . We prove that DC(n) contains n+1 Hamiltonian cycles of the form (upsilon(0,) upsilon(k)(1), .....,upsilon(k)vertical bar v (DC(n))vertical bar-1, upsilon(0)) for 0 <= k <= n, in which v(i)(k) not equal v(i)(k') whenever k not equal k'. The result is optimal since each vertex of DC(n) has only n+1 neighbors.
所屬典藏
期刊論文引用此條目
Shih, Y.-K., Chuang, H.-C., Kao, S.-S., & Tan, J. J. M. (2010). Mutually independent Hamiltonian cycles in dual-cubes. JOURNAL OF SUPERCOMPUTING, 54(2), 239–251. https://doi.org/10.1007/s11227-009-0317-2
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/31999