Group Divisible Covering Designs with Block Size 4: A Type of Covering Array with Row Limit. Issue 8 (6th August 2012)

• Record Type: Journal Article
• Authors: Francetić, Nevena; Danziger, Peter; Mendelsohn, Eric
• Is Part Of: Journal of combinatorial designs. Volume 21:Issue 8(2013:Aug.)
• Page Start: 311
• Page End: 341
• Publication Date: 2012-08-06
• Subjects: Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21324
• Languages: English
• ISSNs: 1063-8539

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A <italic>k</italic>‐<italic>GDCD</italic>, <italic>group divisible covering design</italic>, of type <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpfvq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>g</mml:mi><mml:mi>u</mml:mi></mml:msup></mml:math> is a triple <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg6r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>V</mml:mi><mml:mo>, </mml:mo><mml:mi mathvariant="script">G</mml:mi><mml:mo>, </mml:mo><mml:mi mathvariant="script">B</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>, where <italic>V</italic> is a set of <italic>gu</italic> elements, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg56" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">G</mml:mi></mml:math> is a partition of <italic>V</italic> into <italic>u</italic> sets of size <italic>g</italic>, called <italic>groups</italic>, and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg4n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">B</mml:mi></mml:math> is a collection of <italic>k</italic>‐subsets of <italic>V</italic>, called <italic>blocks</italic>, such that every pair of elements in <italic>V</italic> 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 <italic>CARL</italic>s. 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" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>δ</mml:mi><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math> such that for any positive integers <italic>g</italic> and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpgfm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>≥</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math>, there exists a 4‐<italic>GDCD</italic> of type <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpgd2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>g</mml:mi><mml:mi>u</mml:mi></mml:msup></mml:math> 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" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>g</mml:mi><mml:mo>=</mml:mo><mml:mn>17</mml:mn></mml:mrow></mml:math> and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpg79" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>≡</mml:mo><mml:mn>0</mml:mn><mml:mspace width="0.33em" /><mml:mo>(</mml:mo><mml:mi> mod </mml:mi><mml:mspace width="0.33em" /><mml:mn>3</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>, or (2) <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc66" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>g</mml:mi><mml:mo>≥</mml:mo><mml:mn>8</mml:mn></mml:mrow></mml:math>, <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc7r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>g</mml:mi><mml:mo>≡</mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mn>5</mml:mn><mml:mspace width="0.33em" /><mml:mo>(</mml:mo><mml:mi> mod </mml:mi><mml:mspace width="0.33em" /><mml:mn>6</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>, and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpc89" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>≡</mml:mo><mml:mn>23</mml:mn><mml:mspace width="0.33em" /><mml:mo>(</mml:mo><mml:mi> mod </mml:mi><mml:mspace width="0.33em" /><mml:mn>24</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math> or <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg21fxpd2h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21324:jcd21324-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>∈</mml:mo><mml:mo>{</mml:mo><mml:mn>29</mml:mn><mml:mo>, </mml:mo><mml:mn>35</mml:mn><mml:mo>, </mml:mo><mml:mn>41</mml:mn><mml:mo>}</mml:mo></mml:mrow></mml:math>. To show this, we develop constructions of 4‐<italic>GDCD</italic>s, 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.</p> </abstract>