Binary Covering Arrays on Tournaments

Abstract

We introduce graph-dependent covering arrays which generalize covering arrays on graphs, introduced by Meagher and Stevens (2005), and graph-dependent partition systems, studied by Gargano, Körner, and Vaccaro (1994). A covering array $\hbox{CA}(n; 2, G, H)$ (of strength 2) on column graph $G$ and alphabet graph $H$ is an $n\times |V(G)|$ array with symbols $V(H)$ such that for every arc $ij \in E(G)$ and for every arc $ab\in E(H)$, there exists a  row $\vec{r} = (r_{1},\dots, r_{|V(G)|})$   such that $(r_{i}, r_{j}) = (a,b)$.  We prove bounds on $n$ when $G$ is a tournament graph and $E(H)$ consists of the edge $(0,1)$, which corresponds to a directed version of Sperner's 1928 theorem. For two infinite families of column graphs, transitive and so-called circular tournaments, we give constructions of covering arrays which are optimal infinitely often.