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

Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in [1]: Suppose a graph GG contains one defective edge e∗e∗. Find the endpoints of e∗e∗ by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of e∗e∗ or not. What is then the minimum number c2(G)c2(G) of tests, which are needed in the worst case to identify e∗e∗?In Gerzen (2009) [10], this problem was partially solved by deriving sharp lower and upper bounds for c2(G)c2(G). In addition, it was proved that the determination of c2(G)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 c2c2 and the edge set EE. 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.

► We consider a generalization of the group testing problem for 2 defective items. ► The concept of 2-complexity for graphs is introduced and discussed. ► The graphs with a maximum number of edges by given 2-complexity are explored. ► We characterize such graphs in several ways.