Hamiltonian cycles through prescribed edges in k-ary n-cubes.

Stewart, I.A.

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.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA'11.
• Publication Date: 2011
• Deposit Date: Aug 25, 2011
• Publisher: Springer Verlag
• Volume: 6831
• Pages: 82-97
• Series Title: Lecture Notes in Computer Science Vol. 6831
• Book Title: Combinatorial Optimization and Applications. COCOA 2011.
• DOI: https://doi.org/10.1007/978-3-642-22616-8_8
• Public URL: https://durham-repository.worktribe.com/output/1157712