An application of graph theory to covering arrays
by
Karen Meagher
University of Regina

Covering arrays and covering arrays on graphs are designs that can be used to develop test suites for networks and software. This application makes these designs very practical. Unfortunately, they are difficult to construct and there are few known bounds on their size. If a covering array on a graph exists then there exists a homomorphism from this graph to a particular graph. By considering properties of this particular graph we can determine some restrictions on when a covering arrays exists. This allows us to use techniques from graph theory to determine some existence results on covering arrays and, in some cases, even find some bounds on the optimal size of a covering array.

Paper reference: arXiv:math.CO/0701553

Date received: April 8, 2008