
Elizabeth Maltais

Lucia Moura

Mike Newman
Keywords:
Covering array, Sperner system, Covering array on graph
Abstract
We introduce graphdependent covering arrays which generalize covering arrays on graphs, introduced by Meagher and Stevens (2005), and graphdependent 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 socalled circular tournaments, we give constructions of covering arrays which are optimal infinitely often.