Completing simple partial k-Latin squares

Nicholas Cavenagh, Giovanni Lo Faro, Antoinette Tripodi

Abstract


We study the completion problem for simple k-Latin rectangles, which are a special case of the generalized latin rectangles studied for which embedding theorems are given by Andersen and Hilton (1980) in “Generalized Latin rectangles II: Embedding”, Discrete Mathematics 31(3). Here an  alternative proof of those theorems are given for k-Latin rectangles in  the “simple” case. More precisely, generalizing two classic results on the  completability of partial Latin squares, we prove the necessary and suffisucient conditions for a completion of a simple m x n k-Latin rectangle to a simple k-Latin square of order and we show that if m ≤ n/2, any simple partial k-Latin square of order embeds in a simple k-Latin square of order n.

Keywords


Simple k-Factorization; k-Factor; f-Factor; Multi-Latin Square; k- Latin Square; Completion; Generalized Latin Rectangles

Full Text:

PDF


DOI: http://dx.doi.org/10.1478/AAPP.96S2A4

Copyright (c) 2018 Nicholas Cavenagh, Giovanni Lo Faro, Antoinette Tripodi

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.