DocumentCode
3025726
Title
Mutually independent Hamiltonian cycles in hypercubes
Author
Sun, Chao-Ming ; Lin, Cheng-Kuan ; Huang, Hua-Min ; Hsu, Lih-Hsing
Author_Institution
Dept. of Math., Nat. Central Univ., Chung-li, Taiwan
fYear
2005
fDate
7-9 Dec. 2005
Abstract
A Hamiltonian cycle C of G is described as 1, u2, ..., un(G), u1> to emphasize the order of nodes in C. Thus, u1 is the beginning node and ui is the i-th node in C. Two Hamiltonian cycles of G beginning at u, C1=1, v2, ..., vn(G), v1> and C2=1, u2, ..., un(G), u1>, are independent if u=v1=u1, and vi≠ui for 11, C2, ..., Ck} of G are mutually independent if any two different Hamiltonian cycles are independent. The mutually independent Hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any node u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. Let Qn be the n-dimensional hypercube. We prove that IHC(Qn)=n-1 if n∈{1, 2, 3} and IHC(Qn)=n if n≥4.
Keywords
graph theory; hypercube networks; graph theory; hypercube interconnection network; mutually independent Hamiltonian cycles; Chaos; Computer architecture; Computer networks; Concurrent computing; Hypercubes; Mathematics; Multiprocessor interconnection networks; Network topology; Parallel architectures; Sun; hamiltonian; hypercube; interconnection networks;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures,Algorithms and Networks, 2005. ISPAN 2005. Proceedings. 8th International Symposium on
ISSN
1087-4089
Print_ISBN
0-7695-2509-1
Type
conf
DOI
10.1109/ISPAN.2005.61
Filename
1575872
Link To Document