Mixed covering arrays on 3-uniform hypergraphs

Abstract

Covering arrays are combinatorial objects that have been successfully applied in the design of test suites for testing systems such as software, circuits and networks, where failures can be caused by the interaction between their parameters. Let n and k be positive integers with k >= 3. Three vectors x is an element of Z(g1)(n), y is an element of Z(g2)(n), z is an element of Z(g3)(n) are 3-qualitatively independent if for any triple (a,b,c) is an element of Z(g1) x Z(g2) x Z(g3) there exists an index j is an element of {1, 2,..., n} such that (x(j), y(j), z(j)) = ( a, b, c). Let H be a 3-uniform hypergraph with k vertices v(1), v(2),. . . ,v(k) with respective vertex weights g(1), g(2),, g(k). A mixed covering array on H, denoted by CA (n, H, Pi(k)(i-1) g(i)), is a k x n array such that row i corresponds to vertex v(i), entries in row i are from Z(gi); and if {v(x), v(y), v(z)} is a hyperedge in H, then the rows x, y, z are 3-qualitatively independent. The parameter n is called the size of the array. Given a weighted 3-uniform hypergraph H, a mixed covering array on H with minimum size is called optimal. In this article, we introduce four basic hypergraph operations to construct optimal mixed covering arrays on hypergraphs. Using these operations, we provide constructions for optimal mixed covering arrays on the family of 2-tree hypergraphs, alpha-acyclic 3-uniform hypergraphs, conformal 3-uniform hypertrees having a binary tree as host tree, and 3-uniform loose cycle hypergraphs.