Strongly Hamiltonian laceability of the even k-ary n-cube

✍ Scribed by Chien-Hung Huang

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 218 KB
• Volume: 35
• Category: Article
• ISSN: 0045-7906
• DOI: 10.1016/j.compeleceng.2009.01.002

✦ Synopsis

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N À 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n P 2.