Author :
Sun, Chao-Ming ; Lin, Cheng-Kuan ; Huang, Hua-Min ; Hsu, Lih-Hsing
Author_Institution :
Dept. of Math., Nat. Central Univ., Chung-li, Taiwan
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;
Conference_Titel :
Parallel Architectures,Algorithms and Networks, 2005. ISPAN 2005. Proceedings. 8th International Symposium on