×

Matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes. (English) Zbl 1360.68652

Summary: The \(k\)-ary \(n\)-cube is one of the most popular interconnection networks for parallel and distributed systems. Given an edge set in the \(k\)-ary \(n\)-cube, which conditions guarantee the existence of a Hamiltonian cycle in the \(k\)-ary \(n ~\)-cube containing the edge set? In this paper, we prove for \(n\geqslant 2\) and \(k\geqslant 3\) that every matching having at most \(3n-8\) edges is contained in a Hamiltonian cycle in the \(k\)-ary \(n\)-cube. Also, we present an example to show that the analogous conclusion does not hold for perfect matchings.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI