Mutually independent Hamiltonian cycles in dual-cubes

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2010-11-01

類型

期刊名稱

JOURNAL OF SUPERCOMPUTING

卷期與頁次

第 54 卷,頁 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, 239–251. https://doi.org/10.1007/s11227-009-0317-2

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/150049