Article ID Journal Published Year Pages File Type
4650670 Discrete Mathematics 2008 13 Pages PDF
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
,