Edge Disjoint Hamiltonian Cycles In Twisted N-Cubes

Interconnection is an important aspect of mathematics and computer science research. It is widely used in graph theory, algorithm design and analyse, computer architecture, parallel and discrete computation, computer network and communication, and design of large scale integration circuit. The hypercube and its variations are a kind of interconnected networks model with better structure properties and network parameters, so it is favorite in reseach of interconnection.In this paper, we study the problem of edge disjoint Hamiltonian cycles in the twisted n-cube which is a variation of hypercube. The problem of edge disjoint Hamiltonian cycles is that to search the most Hamiltonian cycles in the graph G, and theedges in distinct Hamiltonian cycles are different each other.Firstly, based on the algorithm of edge-disjoint Hamiltonian cycles in 4-ary n-cube, we use structural recursion to proved a property of 4-ary n-cube combined with Lee-distance Gray-code theory. When n is even, the property can be stated as that the Hamiltonian cycle H₀ derived from h₀ which is presented by Bae and Bose must include the path <0^n-200, 0^n-201, 0^n-202, 0^n-203>. That path is must also included in the Hamiltonian cycle H₀ after edge-transformation from the cycle H'₀ derived from h₀ when n is odd. Secondly, we construct the mapping f to relate 2m-dimensional hypercube with k-ary m-cube and present the Hamiltonian cycle H_o in hypercube mustinclude the path <0^n-200, 0^n-201, 0^n-211, 0^n-210>. Finally, according to the relation of twisted n-cube and hypercube, by the transformation of relevant vertex, we concludedthat there are [n/2] edge disjoint Hamiltonian cycles in twisted n-cubes. And we described concretely how to derived [n/2] edge disjoint Hamiltonian cycles intwisted n-cubes. Thereby we solved the edge-disjoint problem in the twisted n-cubes to some extend.