On a group testing problem: Characterization of graphs with 2-complexity c_2 and maximum number of edges

Kurzfassung

Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988): Suppose a graph G contains one defective edge e*. Find the endpoints of e* by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of e* or not. What is then the minimum number c_2 of tests, which are needed in the worst case to identify e*? This problem was partially solved by Gerzen (2009) by deriving sharp lower and upper bounds for c_2. In addition, it was proved that the determination of c_2 is an NP-complete problem. Among others, it was shown that an uper bound for the number of edges holds for graphs with 2-complexity c_2. In the present paper, we study the class of graphs for which this bound is sharp and characterize these graphs in several ways.