Group Divisible Covering Designs with Block Size 4: A Type of Covering Array with Row Limit. Issue 8 (6th August 2012) - Francetić, Nevena; Danziger, Peter; Mendelsohn, Eric
Abstract A k‐GDCD, group divisible covering design, of type <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpfvq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />gu is a triple <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg6r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(V, G, B), where V is a set of gu elements, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg56" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G is a partition of V into u sets of size g, called groups, and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg4n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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 <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg33" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ>0 such that for any positive integers g and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpgfm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u≥4, there exists a 4‐GDCD of type <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpgd2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />gu which in the worst case exceeds the Schönheim lower bound by δ blocks, except maybe when (1) <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg9d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />g=17 and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg79" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u≡0( mod 3), or (2) <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc66" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />g≥8, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc7r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />g≡2, 5( mod 6), and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc89" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u≡23( mod 24) or <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpd2h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />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.