1. Strongly Hamiltonian laceability of the even k-ary n-cube
- Author
-
Huang, Chien-Hung
- Subjects
- *
HAMILTONIAN graph theory , *INTEGRATED circuit interconnections , *COMPUTER networks , *HYPERCUBES , *BIPARTITE graphs , *MATHEMATICAL proofs , *MATHEMATICAL analysis , *COMPUTER science - Abstract
Abstract: 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 ⩾2. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF