Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420218 | Discrete Applied Mathematics | 2011 | 11 Pages |
Abstract
The kk-ary nn-cube is one of the most popular interconnection networks for parallel and distributed systems. A linear forest in a graph is a subgraph, each component of which is a path. In this paper, we investigate the existence of Hamiltonian cycles passing through linear forests in the kk-ary nn-cube. For any n≥2n≥2 and k≥3k≥3, we show that the kk-ary nn-cube admits a Hamiltonian cycle passing through a linear forest with at most 2n−12n−1 edges.
► The kk-ary nn-cube admits a Hamiltonian cycle passing through a prescribed linear forest. ► The number of edges in the prescribed linear forest does not exceed 2n−12n−1. ► This generalized Dvor˘ák’s results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shiying Wang, Yuxing Yang, Jing Li, Shangwei Lin,