Binary covering arrays on tournaments (Q1648654)

Summary: We introduce graph-dependent covering arrays which generalize covering arrays on graphs, introduced by \textit{K. Meagher} and \textit{B. Stevens} [J. Comb. Theory, Ser. B 95, No. 1, 134--151 (2005; Zbl 1074.05021)], and graph-dependent partition systems, studied by \textit{L. Gargano} et al. [J. Comb. Theory, Ser. A 68, No. 2, 296--316 (1994; Zbl 0807.94008)]. A covering array \(\mathrm{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},\ldots, 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.