Constructing mutually orthogonal symmetric hamiltonian double latin squares from Mullin-Nemeth starters in finite fields

Abstract

Double latin squares—a natural extension of latin squares—were introduced in 2003 by Hilton, et al., in a lengthy paper that explored constructions of these squares with specific properties. Of particular interest are mutually orthogonal symmetric hamiltonian double latin squares of order $2n$, briefly MOSHLS($2n$), because they cannot be constructed by simply joining together four latin squares of order $n$. A proof was originally provided for the existence of MOSHLS($2n$) for all $n\leq 13$. In this paper, we develop a construction of MOSHLS($2q$) for many prime-power values of $q$ using a special family of strong starters known as Mullin-Nemeth starters. We will use the observation of Hilton, et al., that a pair of MOSHLS($2n$) is equivalent to an orthogonal hamilton path decomposition of the complete graph $K_{2n}$.