Structures and lower bounds for binary covering arrays

Abstract

A q-ary t-covering array is an m x 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 Renyi, 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 x 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. (C) 2012 Elsevier B.V. All rights reserved.