Perfect Factorisations of Bipartite Graphs and Latin Squares Without Proper Subrectangles

Abstract

A Latin square is pan-Hamiltonian if every pair of rows forms a single cycle. Such squares are related to perfect 1-factorisations of the complete bipartite graph. A square is atomic if every conjugate is pan-Hamiltonian. These squares are indivisible in a strong sense – they have no proper subrectangles. We give some existence results and a catalogue for small orders. In the process we identify all the perfect 1-factorisations of $K_{n,n}$ for $n\leq 9$, and count the Latin squares of order $9$ without proper subsquares.