Structures and lower bounds for binary covering arrays

Abstract

A $q$-ary $t$-covering array is an $m\times 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 the lower bound of $m$ for a general $t,n$, and $q$. In this article, we show that $m\times 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.

16 pages