Structures and lower bounds for binary covering arrays

A qq-ary tt-covering array is an m×nm×n matrix with entries from {0,1,…,q−1}{0,1,…,q−1} with the property that for any tt column positions, all qtqt possible vectors of length tt occur at least once. One wishes to minimize mm for given tt and nn, or maximize nn for given tt and mm. For t=2t=2 and q=2q=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 mm for a general t,nt,n, and qq. In this article, we show that m×nm×n binary 2-covering arrays under some constraints on mm and nn come from the maximal covering arrays. We also improve the lower bound of Roux for t=3t=3 and q=2q=2, and show that some binary 3 or 4-covering arrays are uniquely determined.