Hamiltonian cycles passing through linear forests in kk-ary nn-cubes

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.