Hamiltonian double Latin squares (Q1403912)

A double Latin square (DLS) of order \(2n\) is a matrix of order \(2n\) in which each of \(n\) symbols occurs exactly twice in each row and twice in each column. Thus a DLS is a particular type of frequency square. In a natural way, each DLS of order \(2n\) encodes a 2-factorisation of the complete bipartite graph \(K_{2n,2n}\). If every 2-factor in that 2-factorisation is a Hamiltonian cycle then the authors say that the DLS in question is an HLS (short for Hamiltonian double Latin square). The concept is similar to one studied by \textit{I. M. Wanless} [Electron. J. Comb. 6, Research paper R9 (1999; Zbl 0915.05023)] and \textit{D. Bryant} et al. [J. Comb. Theory, Ser. A 98, 328-342 (2002; Zbl 1003.05081)]. Both of those papers studied Latin squares (of the ordinary variety, rather than DLSs) which encode perfect 1-factorisations of complete bipartite graphs. The present paper is lengthy and covers a number of different aspects of HLSs, including: (a) Methods of construction, such as a diagonally cyclic method reminiscent of the work of \textit{M. F. Franklin} [Ars Comb. 17, 129-139 (1984; Zbl 0557.05017)]. (b) Orthogonality (in the usual sense for frequency squares). For example, it is shown that for all \(n\geq 2\) there exists a pair of orthogonal HLSs of order \(2n\). (c) Connections with graph theory. It has already been mentioned that a HLS of order \(2n\) encodes a Hamiltonian decomposition of \(K_{2n,2n}\). It is also true that a symmetric HLS of order \(2n\) encodes a Hamiltonian decomposition of \(K_{2n+1}\). Hence many of the results of the paper may be interpreted in graph theoretic terms and many of the proofs are graph theoretic or even matroid theoretic in nature. (d) Embedding results for partial HLSs. Many of these results are proved by the method of amalgamation and detachment.