Cycle switches in Latin squares
Cycle switches are examples of latin interchanges or trades in latin
square designs. They represent minimal changes which can be used to
alter latin squares, and as such have found many applications in the
generation of latin squares. In this paper we construct graphs in
which the vertices are classes of latin squares. Edges arise from
switching cycles to move from one class to another. Such graphs are
constructed on sets of isotopy or main classes of latin squares for
orders up to and including eight. Variants considered are when (i)
only intercalates may be switched, (ii) any row cycle may be switched
and (iii) all cycles may be switched.
The structure of these graphs reveals special roles played by N2,
pan-Hamiltonian, atomic, semi-symmetric and totally-symmetric latin
squares. In some of the graphs parity is important because, for
example, the odd latin squares may be disconnected from the even latin
squares.
An application of our results to the compact storage of large
catalogues of latin squares is discussed. We also prove lower bounds
on the number of cycles in latin squares of both even and odd orders
and show these bounds are sharp for infinitely many orders.
Click here to download the whole paper.
Last modified: Wed Sep 8 13:46:03 EST 2004