Detecting arrays on graphs

Covering arrays on graphs can be used to generate test suites in component-based systems but they cannot identify and determine faulty interactions from the outcome of the test. To address this problem, the notion of detecting arrays on graphs (DAGs) was proposed in this paper. Then, the equivalence and the existence of DAGs were intensively studied. We established a general criterion for measuring the optimality of DAGs in terms of their size. Based on this optimality criterion, the equivalence between optimal DAGs and orthogonal arrays with prescribed properties was established. With this equivalence property, a great number of optimal detecting arrays on cycles were produced by constructing the equivalent combinatorial configurations. In particular, the existence of optimal detecting arrays on cycles with few vertices was almost completely determined.