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.
@article{10_37236_6149,
author = {Elizabeth Maltais and Lucia Moura and Mike Newman},
title = {Binary covering arrays on tournaments},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/6149},
zbl = {1390.05233},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6149/}
}
TY - JOUR
AU - Elizabeth Maltais
AU - Lucia Moura
AU - Mike Newman
TI - Binary covering arrays on tournaments
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/6149/
DO - 10.37236/6149
ID - 10_37236_6149
ER -
%0 Journal Article
%A Elizabeth Maltais
%A Lucia Moura
%A Mike Newman
%T Binary covering arrays on tournaments
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6149/
%R 10.37236/6149
%F 10_37236_6149
Elizabeth Maltais; Lucia Moura; Mike Newman. Binary covering arrays on tournaments. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/6149
