Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles
type: Item
instance of: scholarly article
title: Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles
zbMATH Open document ID: 0915.05023
published in: The Electronic Journal of Combinatorics
publication date: 1999-02-02T00:00:00Z
full work available at URL: https://eudml.org/doc/119791
full work available at URL: v6i1toc.html
review text: A Latin squares of order \(n\) is pan-Hamiltonian if every pair of rows determines a permutation consisting of a single cycle of length \(n\). This is equivalent to saying that the Latin square contains no proper subrectangles. A Latin square is atomic if its six conjugates are all pan-Hamiltonian. Also, there exists a pan-Hamiltonian Latin square of order \(n\) if and only if the complete bipartite graph \(K_{n,n}\) has a perfect 1-factorization. Pan-Hamiltonian Latin squares exist of orders \(n= p\) and \(n= 2p-1\), where \(p\) is prime; there is no such square of even order \(n\geq 4\). If the complete graph \(K_{n+ 1}\) has a perfect 1-factorization, then so does \(K_{n,n}\), and due to the conjectured existence of a perfect 1-factorization of \(K_n\) for all even \(n\), the author conjectures the existence of pan-Hamiltonian Latin squares of all odd orders \(n\). The Latin square \(C_p\) of order \(p\), where \(p\) is prime, consisting of the Caylay table for the cyclic group of order \(p\), is atomic, and the author produces an atomic square of order \(p\) outside the main class of \(C_p\) provided 2 is a primitive root modulo \(p\). The author notes the existence of atomic squares of composite order, citing the square of order 27 constructed from the perfect 1-factorization of \(K_{28}\), but knows of no non-prime power order atomic squares. The author also gives a catalog of pan-Hamiltonian Latin squares of orders up through 9.
reviewed by: Chester J. Salwach
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1247863
zbMATH Keywords: Latin squares
zbMATH Keywords: pan-Hamiltonian
zbMATH Keywords: perfect 1-factorization
zbMATH Keywords: main class
author: Ian M. Wanless
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1247863