Hamiltonian paths in Cartesian powers of directed cycles

DOI10.1007/S00373-002-0519-3MaRDI QIDQ1423491zbMATH OpenOpenAlexFDO

Authors D. Massart

Publication date 4 March 2004

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0110073

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: The vertex set of the kth cartesian power of a directed cycle of length m can be naturally identified with the set of k-tuples of integers modulo m. For any two vertices v and w of this graph, it is easy to see that if there is a hamiltonian path from v to w, then the sum of the coordinates of v is congruent, modulo m, to one more than the sum of the coordinates of w. We prove the converse, unless k = 2 and m is odd.

Recommendations

• scientific article; zbMATH DE number 3943848
• When the cartesian product of directed cycles is Hamiltonian
• Hamilton cycles in a Cartesian product of two directed cycles minus a parallelogrammatic grid
• scientific article; zbMATH DE number 2170432
• Identifying Hamilton cycles in the Cartesian product of directed cycles

Cited in

(3)

• Cut-off for large sums of graphs
• A survey on Hamiltonicity in Cayley graphs and digraphs on different groups
• Hamiltonian paths for involutions in the square of a Cayley graph

This page was built for publication: Hamiltonian paths in Cartesian powers of directed cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1423491)