loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05)
Mutually Independent Hamiltonian Cycles in Hypercubes
Las Vegas, Nevada, USA
December 07-December 09
ISBN: 0-7695-2509-1
Chao-Ming Sun, National Central University Chung-Li, Taiwan
Cheng-Kuan Lin, National Central University Chung-Li, Taiwan
Hua-Min Huang, National Central University Chung-Li, Taiwan
A hamiltonian cycle C of G is described as \left\langle {\mu _1 ,\mu _2 ,....,\mu _n (G),\mu _1 )} \right\rangle to emphasize the order of nodes in C. Thus, \mu _1 is the beginning node and ui is the i-th node in C. Two hamiltonian cycles of G beginning at u, C1 = \left\langle {\mu _1 ,\mu _2 ,....,\mu _n (G),\mu _1 )} \right\rangle and C2 = \left\langle {\mu _1 ,\mu _2 ,....,\mu _n (G),\mu _1 )} \right\rangle , are independent if u = \mu _1 = \mu _1, and \mu _1 \ne \mu _1 for 1 \le i \le n(G). A set of hamiltonian cycles \{ C_1 ,C_2 ,...,C_k \} 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 Q_n be the n-dimensional hypercube. We prove that IHC(Q_n) = n - 1 if n \in {1, 2, 3} and IHC(Q_n) = n if n \ge 4.
Index Terms:
hamiltonian, hypercube, interconnection networks
Citation:
Chao-Ming Sun, Cheng-Kuan Lin, Hua-Min Huang, "Mutually Independent Hamiltonian Cycles in Hypercubes," ispan, pp.504-509, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.