Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube |
| |
Authors: | Shiying Wang Jing Li Ruixia Wang |
| |
Affiliation: | School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi 030006, People’s Republic of China |
| |
Abstract: | The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. |
| |
Keywords: | Hamiltonian paths Hamiltonian cycles Prescribed edges 3-ary n-cubes |
本文献已被 ScienceDirect 等数据库收录! |