Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Iain Stewart

Stewart, 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.

Author(s) from Durham

Abstract

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.