標題: Mutually independent Hamiltonian cycles in dual-cubes
作者: Shih, Yuan-Kang
Chuang, Hui-Chun
Kao, Shin-Shin
Tan, Jimmy J. M.
資訊工程學系
Department of Computer Science
關鍵字: Hypercube;Dual-cube;Hamiltonian cycle;Hamiltonian connected;Mutually independent
公開日期: 1-十一月-2010
摘要: 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.
URI: http://dx.doi.org/10.1007/s11227-009-0317-2
http://hdl.handle.net/11536/150049
ISSN: 0920-8542
DOI: 10.1007/s11227-009-0317-2
期刊: JOURNAL OF SUPERCOMPUTING
Volume: 54
起始頁: 239
結束頁: 251
顯示於類別:期刊論文