Binary covering arrays on tournaments
type: Item
instance of: scholarly article
title: Binary covering arrays on tournaments
zbMATH Open document ID: 1390.05233
author: Elizabeth Maltais
author: Lucia Moura
author: Mike Newman
published in: The Electronic Journal of Combinatorics
publication date: 2018-06-27T00:00:00Z
full work available at URL: v25i2p47
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 6895330
zbMATH Keywords: covering array
zbMATH Keywords: Sperner system
zbMATH Keywords: covering array on graph
MaRDI profile type: Publication
cites work: Q3594048
cites work: Sperner capacities
cites work: Capacities: From information theory to extremal set theory
cites work: Q4828516
cites work: Two applications (for search theory and truth functions) of Sperner type theorems
cites work: Families of \(k\)-independent sets
cites work: Covering arrays on graphs
description: scientific article; zbMATH DE number 6895330