Search problems on graphs (Q1082080): Difference between revisions

The following search problem on graphs is studied: given a graph \(G=(V,E)\) and an unknown edge \(e\in E\), we can test whether a subset \(A\leq V\) contains both ends of e, one end, or neither. The edge e is to be located with the minimum number of tests. When G is a complete graph, this is a classical problem of finding ''defectives'' in a population when at most two defectives are present. Lower and upper bounds for the minimum number of tests are derived for complete graphs and for complete bipartite graphs. These give the exact values for \(K_{m,n}\), \(1\leq m\leq 4\).