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

fYear

2010

fDate

6-9 Sept. 2010

Firstpage

24

Lastpage

28

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 Q_n, 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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ISPA.2010.28

Filename

5634405