A search problem on graphs which generalizes some group testing problems with two defectives (Q1176719): Difference between revisions

The author studies the problem of searching for an edge in a graph and tries to characterize classes of graphs with edges where \([\log_ 2 m]\) tests suffice to find an arbitrary edge. Graphs having this property are called 2-optimal. Among other results it is shown that graphs are 2- optimal, if they are 2-orderable, i.e. their vertices can be arranged in a sequence \(v_ 1,\dots,v_ n\) such that each \(v_ i\) has at most 2 direct neighbours among \(v_ 1,\dots,v_{i-1}\). Furthermore, several upper bounds are given for the maximum number of tests in a search.