Hamilton-like Properties Of K-Ary N-Cubes

Research of interconnection is an important aspect of mathematics and computer science. 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. k-ary n-cube is a very popular topology of networks. Ring, mesh and hypercube are all its special cases. It has been used in the design of several concurrent computers, including the J-Machine, the Mosaic, the iWarp, and so on. Network parameters and topological properties of k-ary n-cubes are firstly systematically introduced and then its some Hamilton-like properties are investigated .The conclusions are as follows:(1) By regularity and symmetry of k-ary 2-cube, a method of constructing (almost) Hamilton path between any two different vertices is presented, thereby the following conclusions are proved:(i) Q^k₂ is (almost) Hamilton- connectivity; (ii) Q^k₂ is bipanconnected; (iii) Q^k₂ is bipancyclic;(iv) If k is odd, there are all odd cycles from k to |V(Q^k₂)| besides all even cycles from 4 to |V(Q^k₂)|-1 in Q^k₂ .(2) Using conclusion in (1), connectivity of Q^k_n is proved: (i) For any n ≥ 3 , Q^k_n is (almost) Hamilton- connectivity; (ii) If k is odd, Q^k_n is Hamilton-connectivity.