Pseudo-Cartesian products and Hamiltonian decompositions of Cayley graphs on abelian groups (Q1815310): Difference between revisions

The reviewer has posed the problem [Research problem 59, Discrete Math. 50, 115 (1984)] of whether or not every connected Cayley graph on a finite abelian group has a Hamilton decomposition, that is, a partition of the edge set into Hamilton cycles. The Cayley graph \(X(G;S)\) on the finite abelian group \(G\) with connection set \(S\) is the graph whose vertices are labelled by the elements of \(G\) with an edge joining \(x\) and \(y\) if and only if either \(x-y\) or \(y-x\) belongs to \(S\). With this definition, it is assumed that \(s\in S\) and \(\text{ord}(s)\neq 2\) imply \(s^{-1}\not\in S\). The authors consider 6-regular Cayley graphs on abelian groups. They obtain Hamilton decompositions for a variety of conditions on the connection sets. The conditions cover `most' cases. In the process of establishing their results, they include a complete proof of the 4-regular case and prove that pseudo-Cartesian products of two cycles have Hamilton decompositions.