Multiple-Ply Hamiltonian Graphs and Digraphs

A digraph is said to be k-ply hamiltonian if it admits k arc-disjoint Hamilton circuits. In this paper we determine when the Cayley digraph Cay(S) is 2-ply hamiltonian in the case where S is a two-element generating set for an abelian group. This result has several applications; for example, it can be used to determine when the Cartesian product DC r × DC s of two circuits is decomposable into two Hamilton circuits. We also study infinite digraphs, and characterize those infinite vertex transitive digraphs which can be decomposed into an infinite number of Hamilton paths.