Embedding Hamiltonian Paths with Prescribed Linear Forests into k-ary n-Cube Networks

Graph embedding is a fundamental problem in computer science. Let Formula: see text (resp., Formula: see text) be the interconnection network for a parallel computer system Formula: see text (resp., Formula: see text). If Formula: see text could be embedded into Formula: see text, then Formula: see text can simulate Formula: see text’s behavior. The Formula: see text-ary Formula: see text-cube Formula: see text is a node-symmetric and link-symmetric recursive interconnection network for parallel computer systems. Let Formula: see text be a prescribed linear forest of Formula: see text, and let Formula: see text and Formula: see text be any two distinct nodes in Formula: see text such that Formula: see text has no path with Formula: see text or Formula: see text as internal nodes, or both as end-nodes. This paper shows that there is a Hamiltonian path passing through Formula: see text between Formula: see text and Formula: see text in Formula: see text with Formula: see text and odd Formula: see text even if the number of links in Formula: see text is up to Formula: see text.