zbMATH — the first resource for mathematics

Symmetries that Latin squares inherit from 1-factorizations. (English) Zbl 1067.05061
A rooted 1-factorization, \((F,v)\), of the complete graph \(K_{n+1}\), with \(n\) odd, consists of a 1-factorization \(F\) of \(K_{n+1}\) along with a vertex \(v\) from \(K_{n+1}\), called the root, and a total order on the vertices of \(K_{n+1}\). The authors make use of the well-known \(\mathbb K\)-construction to obtain an ordered 1-factorization of the complete bipartite graph \(K_{n,n}\) and then a Latin square of order \(n\) denoted by \({\mathcal L}(F,v)\), which is shown to be symmetric and idempotent, by not necessarily totally symmetric. Conversely, any symmetric idempotent Latin square of order \(n\) is proven to be \({\mathcal L}(F,v)\) for some \((F,v)\) of \(K_{n+1}\). They establish a number of results concerning the autotopies which \({\mathcal L}(F,v)\) can possess. In particular, the automorphism group of \({\mathcal L}(F,v)\) is isomorphic to the stabilizer of \(v\) in the automorphism group of \(F\). Their main result is that the three assertions: \({\mathcal L}(F,u)\) is paratopic to \({\mathcal L}(G,v)\), \({\mathcal L}(F,u)\) is isomorphic to \({\mathcal L}(G,v)\), and \((F,u)\) is isomorphic to \((G,v)\), are equivalent. They also provide an algorithm that can determine in \(O(n^3)\) time whether a Latin square of order \(n\) is paratopic to an \({\mathcal L}(F,v)\), or whether it is isotopic to a symmetric or totally symmetric Latin square.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B15 Orthogonal arrays, Latin squares, Room squares
05-04 Software, source code, etc. for problems pertaining to combinatorics
Full Text: DOI
[1] Bryant, J Combin Theory Ser A 98 pp 328– (2002)
[2] and New families of atomic Latin squares and perfect one-factorisations, submitted for publication.
[3] Cameron, Bull London Math Soc 25 pp 1– (1993)
[4] and Triple systems, Clarendon, Oxford, 1999.
[5] Dénes, Ars Combin 25A pp 109– (1988)
[6] and Latin squares and their applications, Akadémiai Kiadó, Budapest, 1974.
[7] and Latin squares: New developments in the theory and applications, Annals Discrete Math, Vol. 46, North-Holland, Amsterdam, 1991. · Zbl 0715.00010
[8] Duncan, J Combin Des 2 pp 341– (1994)
[9] Ihrig, J Combin Des 11 pp 124– (2003)
[10] Keedwell, Utilitas Math 14 pp 141– (1978)
[11] Groupoids and partitions of complete graphs, Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 215-221.
[12] Laufer, Ars Combin 9 pp 43– (1980)
[13] Maenhaut, J Combin Des 12 pp 12– (2004)
[14] Owens, Ars Combin 44 pp 137– (1996)
[15] Petrenyuk, Cybernetics 16 pp 6– (1980)
[16] Sade, Math Nachr 20 pp 73– (1959)
[17] Sade, Univ Lisboa Revista Fac Ci A 11 pp 121– (1964)
[18] Group theory II, Grundlehren der Mathematischen Wissenschaften, 248, Springer-Verlag, New York, 1986.
[19] Wanless, Electron J Combin 6 pp r9– (1999)
[20] Atomic latin squares based on cyclotomic orthomorphisms, (submitted for publication).
[21] One-factorizations, Math Appl, Vol. 390, Kluwer Academic, Dordrecht, 1997. · doi:10.1007/978-1-4757-2564-3
[22] Xu, IEEE Trans Inform Theory 45 pp 1817– (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.