On some covering designs

Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which $\text{C(n, k, t) ?}\text{3(t + 1)}\text{2}$ [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case $\text{3(t + 1)}\text{2}\text{< C(n, k, t) ?}\text{3(t + 2)}\text{2}$.     

New constructions for covering designs

A(v, k, t) covering design, or covering, is a family of k-subnets, called blocks, chosen from a v-set, such that each t-subnet is contained in at least one of the blocks. The number of blocks is the covering's size, and the minimum size of such a covering is denoted by C(v,k,t). This paper gives three new methods for constructing good coverings; a greedy algorithm similar to Conway and Sloane's algorithm for lexicographic codes [6], and two methods that synthesize new coverings from preexisting ones. Using these new methods, together with results in the literature, we build tables of upper bounds on C(v,k,t) for v ? 32, k ? 16, and t ? 8. © 1995 John Wiley & Sons, Inc.     

Small covering designs by branch-and-cut

 A Branch-and-Cut algorithm for finding covering designs is presented. Its originality resides in the use of isomorphism pruning of the enumeration tree. A proof that no 4-(10, 5, 1)-covering design with less than 51 sets exists is obtained together with all non isomorphic 4-(10, 5, 1)-covering designs with 51 sets. Received: August 16, 2000 / Accepted: July 18, 2001 Published online: September 5, 2002     

Kirkman covering designs with even-sized holes

A Kirkman holey covering design, denoted by KHCD(g^u), is a resolvable group-divisible covering design of type g^u. Each of its parallel class contains one block of size δ, while other blocks have size 3. Here δ is equal to 2, 3 and 4 when gu≡2, 3 and 4 (mod 3) in turn. In this paper, we study the existence problem of a KHCD(g^u) which has minimum possible number of parallel classes, and give a solution for most values of even g and u.     

Generalized covering designs and clique coverings

Inspired by the “generalized t‐designs” defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835–4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:378‐406, 2011     

Pair covering designs with block size 5

In this article we look at pair covering designs with a block size of 5 and . The number of blocks in a minimum covering design is known as the covering number C(v,5,2). For v?24, these values are known, and all but v=8 exceed the Schönheim bound, L(v,5,2)=⌈v/5⌈(v-1)/4⌉⌉. However, for all v?28 with , it seems probable that C(v,5,2)=L(v,5,2). We establish this for all but 17 possible exceptional values lying in the range 40?v?280.     

Group divisible covering designs with block size four

Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type $g^u$ is a covering number denoted by $C(k,g^u)$. When $k=3$, the values of $C(3,g^u)$ have been determined completely for all possible pairs $(g,u)$. When $k=4$, Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type ${(g,h)}^u$. Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for $(g,u)$ whose status remains undetermined arise when $g\equiv 7mod12$ and $u\equiv 3mod6$, when $g\equiv 11,14,17,23mod24$ and $u\equiv 5mod6$, and in several small families for which one of g and u is fixed.     

On covering designs with block size 5 and index 5

LetV be a finite set of order . A (, , ) covering design of index and block size is a collection of -element subsets, called blocks, such that every 2-subset ofV occurs in at least blocks. The covering problem is to determine the minimum number of blocks, (, , ), in a covering design. It is well known that , where [x] is the smallest integer satisfyingx[X]. It is shown here that (, 5, 5)=(, 5, 5) for all positive integers 5 with the possible exception of =24, 28, 56, 104, 124, 144, 164, 184.     

On small packing and covering designs with block size 4

A packing (respectively covering) design of order v, block size k, and index λ is a collection of k-element subsets, called blocks, of a v-set, V, such that every 2-subset of V occurs in at most (at least) λ blocks. The packing (covering) problem is to determine the maximum (minimum) number of blocks in a packing (covering) design. Motivated by the recent work of Assaf [1] [2], we solve the outstanding packing and covering problems with block size 4.     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

Kirkman packing and covering designs with spanned holes of size 2

A Kirkman holey packing (resp. covering) design, denoted by KHPD(g^u) (resp. KHCD(g^u)), is a resolvable (gu, 3, 1) packing (resp. covering) design of pairs with u disjoint holes of size g, which has the maximum (resp. minimum) possible number of parallel classes. Each parallel class contains one block of size δ, while other blocks have size 3. Here δ is equal to 2, 3, and 4 when gu ≡ 2, 3, and 4 (mod 3) in turn. In this paper, the existence problem of a KHPD(2^u) and a KHCD(2^u) is solved with one possible exception of a KHPD(2⁸). © 2004 Wiley Periodicals, Inc.     

On the non-existence of pair covering designs with at least as many points as blocks

We establish new lower bounds on the pair covering number C _λ (υ,k) for infinitely many values of υ, k and λ, including infinitely many values of υ and k for λ=1. Here, C _λ (υ,k) denotes the minimum number of k-subsets of a υ-set of points such that each pair of points occurs in at least λ of the k-subsets. We use these results to prove simple numerical conditions which are both necessary and sufficient for the existence of (K _k − e)-designs with more points than blocks.     

On upper bounds for code distance and covering radius of designs in polynomial metric spaces

The purpose of this paper is to present new upper bounds for code distance and covering radius of designs in arbitrary polynomial metric spaces. These bounds and the necessary and sufficient conditions of their attainability were obtained as the solution of an extremal problem for systems of orthogonal polynomials. For antipodal spaces the behaviour of the bounds in different asymptotical processes is determined and it is proved that this bound is attained for all tight 2k-design.     

3-(v, 4, 1) covering designs with chromatic numbers 2 and 3

A t-(v, k, λ) covering design is a pair (X, B) where X is a v-set and B is a collection of k-sets in X, called blocks, such that every t element subset of X is contained in at least λ blocks of B. The covering number, C_λ(t, k, v), is the minimum number of blocks a t-(v, k, λ) covering design may have. The chromatic number of (X, B) is the smallest m for which there exists a map φ: X → Z_m such that ∣φ((β)∣ ≥2 for all β ∈ B, where φ(β) = {φ(x): x ∈ β}. The system (X, B) is equitably m-chromatic if there is a proper coloring φ with minimal m for which the numbers ∣φ^?1(c)∣ c ∈ Z_m differ from each other by at most 1. In this article we show that minimum, (i.e., ∣B∣ = C λ (t, k, v)) equitably 3-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0 (mod 6), v ≥ 18 for v ≥ 1, 13 (mod 36), v ≡ 13 and for all numbers v = n, n + 1, where n ≡ 4, 8, 10 (mod 12), n ≥ 16; and n = 6.5^a 13^b 17^c ?4, a + b + c > 0, and n = 14, 62. We also show that minimum, equitably 2-chromatic 3-(v, 4, 1) covering designs exist for v ≡ 0, 5, 9 (mod 12), v ≥ 0, v = 2.5^a 13^b 17^c + 1, a + b + c > 0, and v = 23. © 1993 John Wiley & Sons, Inc.