A SEARCH PROBLEM ON GRAPHS WHICH GENERALIZES SOME GROUP-TESTING PROBLEMS WITH 2 DEFECTIVES

We consider a search problem which generalizes the group testing problems previously studied in papers of Chang/Hwang and Chang/Hwang/Lin. In its general form for arbitrary graphs the problem was proposed by Aigner. Let G be a finite simple graph with vertex-set V(G) and edge-set E(G). Let e* is-a-member-of E(G) be an unknown edge. In order to find e* we choose a sequence of test-sets A subset-or-is-equal-to V(G) where after every test we are told whether or not e* is an edge of the subgraph induced by A. Find the minimum number c(G) of tests required. G is called 2-optimal if c(G) achieves the usual information theoretic lower bound, i.e., c(G) = [log2\E(G)\]. It was shown by Chang and Hwang that all complete bipartite graphs are 2-optimal and Aigner observed that forests are 2-optimal. In the present paper we relate the parameter c(G) to the notion of a k-orderable graph. (We call G k-orderable if there exists a linear order upsilon-1,..., upsilon-n of the vertices of G such that each upsilon-i has at most k neighbors among upsilon-1,..., upsilon-i-1; this is equivalent to saying that the well known coloring number of G introduced by Erdos and Hajnal is at most k + 1.) Among other results we show that 2-orderable graphs are 2-optimal and provide upper bounds for c(G).