2005/09/19 by Karola Mészáros, Karola Meszaros, Meszaros, Karola
Computer Science · Engineering · Mathematics · #05B15 #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05B15
paper · pdf · doi:10.48550/arxiv.math/0509410
16 pages, 24 figures
arxiv created 2005/09/19 · openalex publication_date 2005/09/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Latin square L(n,k) is a square of order n with its entries colored with k colors so that all the entries in a row or column have different colors. Let d(L(n,k)) be the minimal number of colored entries of an n × n square such that there is a unique way of coloring of the yet uncolored entries in order to obtain a Latin square L(n, k). In this paper we discuss the properties of d(L(n,k)) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(L(n, 2n-1))=n2-n, which holds for even n, and we establish the new result d(L(n, 2n-2)) ≥ n2-\lfloor(8n)/(5)\rfloor and show that this bound is tight for n divisible by 10.