Completing simple partial k-Latin squares

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 n and we show that if m ≤ n/2, any simple partial k-Latin square P of order m embeds in a simple k-Latin square L of order n.