Mixed covering arrays on graphs

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. Let k and n be positive integers, and let G be a graph with k vertices v 1 , v 2 ,…, v k with respective vertex weights g 1 ≤ g 2 ≤ … ≤ g k . A mixed covering array on G , denoted by $CA( {n,G,\;\prod\nolimits_{i = 1}^k {g_i } } )$ , is an n × k array such that column i corresponds to v i , cells in column i are filled with elements from ℤ g i and every pair of columns i , j corresponding to an edge v i , v j in G has every possible pair from ℤ g i × ℤ g j appearing in some row. The number of rows in such array is called its size . Given a weighted graph G , a mixed covering array on G with minimum size is called optimal . 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