Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650670 | Discrete Mathematics | 2008 | 13 Pages |
Abstract
A generalized Latin square of type (n,k)(n,k) is an n×nn×n array of symbols 1,2,…,k1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k)d(n,k) denote the cardinality of the minimal set S of given entries of an n×nn×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k)(n,k). In this paper we discuss the properties of d(n,k)d(n,k) for k=2n-1k=2n-1 and k=2n-2k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n2-nd(n,2n-1)=n2-n, which holds for even nn, and we establish the new result d(n,2n-2)⩾n2-⌊8n5⌋. We also show that the latter bound is tight for nn divisible by 10.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Karola Mészáros,