A ternary search problem on graphs (Q1118418): Difference between revisions

Consider a graph in which one edge is defective. To search for this edge, one 2-colours the vertices and is told whether the defective edge has both ends of colour 1, both of colour 2, or one of each. One repeats this test on subsets of the edges until the defective edge is found; for a q- edge graph, at least \([\log_ 3 q]\) tests are necessary. In this paper, the author shows that for forests of maximum degree r, one needs at most \(t+1-[\log_ 3(2^ t+1)]\) tests more than the minimum where t satisfies \(2^ t<r\leq 2^{t+1}\). He conjectures that for each r, there are only finitely many forests of maximum degree r in which \([\log_ 3 q]\) tests do not suffice, and proves this for \(r=3\).