×

zbMATH — the first resource for mathematics

Hamiltonian paths in Cartesian powers of directed cycles. (English) Zbl 1032.05069
Summary: The vertex set of the \(k\)th Cartesian power of a directed cycle of length \(m\) can be naturally identified with the abelian group \((\mathbb Z_m)^k\). For any two elements \(u=(u_1,\dots,u_k)\) and \(v=(v_1,\dots,v_k)\) of \((\mathbb Z_m)^k\), it is easy to see that if there is a Hamiltonian path from \(u\) to \(v\), then \(u_1+\cdots+u_k \equiv v_1+\cdots+v_k+1\pmod m\). We prove the convers, unless \(k=2\) and \(m\) is odd.

MSC:
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI arXiv