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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.61
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||