Group divisible covering designs with block size 4: A type of covering array with row limit

摘要

A k-GDCD, group divisible covering design, of type gu is a triple (V,G,B), where V is a set of gu elements, G is a partition of V into u sets of size g, called groups, and B is a collection of k-subsets of V, called blocks, such that every pair of elements in V is either contained in a unique group or there is at least one block containing it, but not both. This family of combinatorial objects is equivalent to a special case of the graph covering problem and a generalization of covering arrays, which we call CARLs. In this paper, we show that there exists an integer δ>0 such that for any positive integers g and u≥4, there exists a 4-GDCD of type gu which in the worst case exceeds the Sch?nheim lower bound by δ blocks, except maybe when (1) g=17 and u≡0(mod 3), or (2) g≥8, g≡2,5(mod 6), and u≡23(mod 24) or u{29,35,41}. To show this, we develop constructions of 4-GDCDs, which depend on two types of ingredients: essential, which are used multiple times, and auxiliary, which are used only once in the construction. If the essential ingredients meet the lower bound, the products of the construction differ from the lower bound by as many blocks as the optimal size of the auxiliary ingredient differs from the lower bound.