Title :
The Existence of Two Mutually Independent Hamiltonian Cycles in Hypercube-Like Graphs
Author :
Peng, Yen-Neng ; Lai, Pao-Lien ; Tsai, Chang-Hsiung ; Hsu, Hong-Chun
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Dong Hwa Univ., Shoufeng, Taiwan
Abstract :
The problem of whether or not there are mutually independent hamiltonian cycles in interconnection networks has attracted a great attention in recent years. In this paper, we will show that most of n-dimensional hypercube-like graphs have two mutually independent hamiltonian cycles. Moreover, we also develop a systematic linear time algorithm for constructing two mutually independent hamiltonian cycles in the n-dimensional hypercube Qn, n > 3.
Keywords :
directed graphs; hypercube networks; hypercube like graphs; interconnection networks; mutually independent hamiltonian cycles; n-dimensional hypercube like graphs; systematic linear time algorithm; Bipartite graph; Color; Hypercubes; Parallel algorithms; Reflective binary codes; USA Councils; algorithm; gray code; hamiltonian cycle; hypercube; hypercuke-like network; interconnection networks; mutually independent; reflected link string;
Conference_Titel :
Parallel and Distributed Processing with Applications (ISPA), 2010 International Symposium on
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-8095-1
Electronic_ISBN :
978-0-7695-4190-7
DOI :
10.1109/ISPA.2010.28
