Combinatorial Group Testing in Bipartite Graphs

The method of large scale group testing has been used in the economical testing of blood samples, and in non-testing situations such as experimental designs and coding theory, for over 50 years. Some very basic questions addressing the minimum number of tests required to identify defective samples still remain unsolved, including the situation where one defective sample in each of two batches are to be found. This gives rise to an intriguing graph theoretical conjecture concerning bipartite graphs, a conjecture which in this paper is proved to be true in the case where vertices in one part of the bipartite graph have low degree.