Hamilton decompositions of one-ended Cayley graphs

Abstract

We prove that any one-ended, locally finite Cayley graph with non-torsion generators admits a decomposition into edge-disjoint Hamiltonian (i.e. spanning) double-rays. In particular, the $n$-dimensional grid ${\mathbb{Z}}^n$ admits a decomposition into $n$ edge-disjoint Hamiltonian double-rays for all $n\in \mathbb{N}$.

17 pages, 4 figures