Premium
On asymmetric coverings and covering numbers
Author(s) -
Applegate David,
Rains E. M.,
Sloane N. J. A.
Publication year - 2003
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.10022
Subject(s) - combinatorics , mathematics , set (abstract data type) , computer science , programming language
An asymmetric covering ${\cal D}(n,R)$ is a collection of special subsets S of an n ‐set such that every subset T of the n ‐set is contained in at least one special S with $|S| - |T| \le R$ . In this paper we compute the smallest size of any ${\cal D}(n,1)$ for $n \le 8.$ We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers $C(n,k,k-1)$ , and we determine the following new values: $C(10,5,4) = 51$ , $C(11,7,6) =84 $ , $C(12,8,7) = 126 $ , $C(13,9,8)= 185$ , and $C(14,10,9) = 259$ . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022