Cycle Switches in Latin Squares
Cycle Switches in Latin Squares
复制标题
拉丁方中的循环开关
DOI：
10.1007/s00373-004-0567-7
复制
发表时间：
2004
影响因子：
0.7
通讯作者：
Ian M. Wanless
中科院分区：
文献类型：
--
作者：
Ian M. Wanless
循环开关是可以用来改变拉丁方的最简单的变化，因此在拉丁方的生成中有许多应用。他们还提供了最简单的例子，拉丁交流或贸易拉丁广场设计。在本文中，我们构造的图的顶点是类拉丁方。边缘来自于从一个类移动到另一个类的切换周期。这样的图被构造在合痕集或拉丁方的主类上，其阶数为8。考虑的变体是当（i）仅嵌入物可以被切换，（ii）任何行循环可以被切换和（iii）所有循环可以被切换时。这些图的结构揭示了N2、泛哈密顿、原子、半对称和全对称拉丁方所起的特殊作用。在某些图中，奇偶性很重要，因为例如，奇数拉丁方可能与偶数拉丁方不相连。我们的结果的应用，以紧凑的存储大型目录拉丁广场进行了讨论。我们还证明了拉丁方的偶数和奇数阶的循环数的下界，并表明这些界是尖锐的无穷多个订单。
Cycle switches are the simplest changes which can be used to alter latin squares, and as such have found many applications in the generation of latin squares. They also provide the simplest examples of latin interchanges or trades in latin square designs. 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 byN2, 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.