Hamilton decompositions of directed cubes and products (Q2509294)

Given a graph \(X\), let \(\overleftrightarrow{X}\) denote the directed graph one obtains by replacing each edge \(uv\) of \(X\) with an arc in each direction between \(u\) and \(v\). If \(X\) admits a decomposition into Hamilton cycles, it is obviously the case that \(\overleftrightarrow{X}\) admits a decomposition into Hamilton directed cycles. However, when \(X\) is a regular graph with odd valency, then the problem of determining whether \(\overleftrightarrow{X}\) has a Hamilton decomposition becomes rather interesting. For example, it is not difficult to show that \(\overleftrightarrow{Q}_3\) does not have a Hamilton decomposition, where \(Q_3\) is the 3-dimensional cube, but it was thought that \(\overleftrightarrow{Q}_{2m+1}\) may have a Hamilton decomposition for all \(m>1\). (As far as the reviewer knows, the author of this paper was the first person to pose the question about the cubes of odd dimension.) In this nice paper, the author goes well beyond the question about the odd-dimensional cubes. He determines a sufficient condition on \(X\) so that the Cartesian product of \(\overleftrightarrow{X}\), \(\overleftrightarrow{C_n}\), and \(\overleftrightarrow{K_1}\) has a Hamilton decomposition. As a special case, \(\overleftrightarrow{Q}_{2m+1}\) has a Hamilton decomposition for all \(m>1\).