Monotonicity of the search number in the Golovach problem
T. V. Abramovskaya, Н. Н. Петров · Vestnik St Petersburg University Mathematics · 2011
The Golovach problem, also known as the ɛ-search problem, is as follows. A team of pursuers pursues an evader on a topological graph. The objective of the pursuers is to catch the evader, that is, approach the evader to a distance not exceeding a given nonnegative number ɛ. It is assumed that the evader is invisible to the pursuers and is fully informed beforehand about the search program of the pursuers. The problem is to find the ɛ-search number, i.e., the least number of pursuers sufficient for capturing the evader. Graphs with monotone ɛ-search number are studied; the ɛ-search number of a graph G is said to be monotone if it is not exceeded by the ɛ-search numbers of all connected subgraphs H of G . It is known that the ɛ-search number of any tree is monotone for all nonnegative ɛ. The edgesearch number, which is equal to the 0-search number, is monotone for all connected subgraphs of an arbitrary graph. A sufficient monotonicity condition for the ɛ-search number of any graph is obtained. This result is improved in the case of complete subgraphs. The Golovach function is constructed for graphs obtained by removing one edge from complete graphs with unit edges.