Structures and lower bounds for binary covering arrays

A q -ary t -covering array is an m × n matrix with entries from { 0 , 1 , … , q − 1 } with the property that for any t column positions, all q t possible vectors of length t occur at least once. One wishes to minimize m for given t and n , or maximize n for given t and m . For t = 2 and q = 2 , it is completely solved by Rényi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found a lower bound of m for a general t , n , and q . In this article, we show that m × n binary 2-covering arrays under some constraints on m and n come from the maximal covering arrays. We also improve the lower bound of Roux for t = 3 and q = 2 , and show that some binary 3 or 4-covering arrays are uniquely determined.