Publication details for Professor Iain StewartStewart, I.A. (2011), Hamiltonian cycles through prescribed edges in k-ary n-cubes, in Wang, W., Zhu, X. & Du, D.-Z. eds, Lecture Notes in Computer Science Vol. 6831 6831: 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA'11. Zhangjiajie, China, Springer, Berlin, 82-97.
- Publication type: Conference Paper
- ISSN/ISBN: 9783642226151, 9783642226168, 0302-9743
- DOI: 10.1007/978-3-642-22616-8_8
- Further publication details on publisher web site
Author(s) from Durham
We prove that if P is a set of at most 2n − 1 edges in a k-ary n-cube, where k ≥ 4 and n ≥ 2, then there is a Hamiltonian cycle on which every edge of P lies if, and only if, the subgraph of the k-ary n-cube induced by the edges of P is a vertex-disjoint collection of paths. This answers a question posed by Wang, Li and Wang who proved the analogous result for 3-ary n-cubes.