Mixed covering arrays on graphs
Karen Meagher, Lucia Moura, Latifa Zekaoui · Journal of Combinatorial Designs · 2007
Abstract Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Letkandnbe positive integers, and letGbe a graph withkverticesv1,v2,…,vkwith respective vertex weightsg1≤g2≤ … ≤gk. Amixed covering arrayonG, denoted by$CA( {n,G,\;\prod olimits_{i = 1}^k {g_i } } )$ , is ann×karray such that columnicorresponds tovi, cells in columniare filled with elements from ℤgiand every pair of columnsi,jcorresponding to an edgevi,vjinGhas every possible pair from ℤgi× ℤgjappearing in some row. The number of rows in such array is called itssize. Given a weighted graphG, a mixed covering array onGwith minimum size is calledoptimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007