z-logo
Premium
Mixed covering arrays on graphs
Author(s) -
Meagher Karen,
Moura Lucia,
Zekaoui Latifa
Publication year - 2007
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20149
Subject(s) - combinatorics , mathematics , bipartite graph , vertex (graph theory) , alphabet , graph , row , discrete mathematics , computer science , philosophy , linguistics , database
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here