Name
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, Korner, and Vaccaro (1994). A covering array CA(n; 2; G;H) (of strength 2) on column graph G and alphabet graph H is an n x vertical bar V (G)vertical bar array with symbols V (H) such that for every arc ij is an element of E (G) and for every arc ab 2 is an element of (H), there exists a row (r) over right arrow = (r(1); ... ;r (vertical bar V (G)vertical bar)) 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. |
Year | Venue | Field |
|---|---|---|
2018 | ELECTRONIC JOURNAL OF COMBINATORICS | Graph,Discrete mathematics,Combinatorics,Tournament,Partition (number theory),Mathematics,Binary number,Alphabet,Transitive relation |
DocType | Volume | Issue |
Journal | 25 | 2 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elizabeth Maltais | 1 | 2 | 1.39 |
| Lucia Moura | 2 | 99 | 17.78 |
| Mike Newman | 3 | 38 | 5.81 |