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

AbstractConsider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in [1]: 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 c2(G) of tests, which are needed in the worst case to identify e∗?In Gerzen (2009) [10], this problem was partially solved by deriving sharp lower and upper bounds for c2(G). In addition, it was proved that the determination of c2(G) is an NP-complete problem. Among others, it was shown that the inequality |E|≤4(c2−12)+4=2c22−6c2+8 holds for graphs with 2-complexity c2 and the edge set E. In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization