Nontrivial discontinuities of the Golovach functions for trees (Q1759468)

In the \(\varepsilon\)-search problem on a connected topological graph we considered team of pursuers \(P_1,\dots,P_k\) trying to capture the invisible evader \(E\), who, in turn, tries to escape. It is assumed that the evader is captured by a pursuer if they are a distance not exceeding a given nonnegative \(\varepsilon\) apart. Solution of the problem, \textit{the \(\varepsilon\)-search number}, is the minimum number of pursuers required to successfully complete \(\varepsilon\)-search. Properties of the Golovach function, which associates each nonnegative number \(\varepsilon\) with the \(\varepsilon\)-search number, are studied. It is known that the Golovach function is piecewise constant, nonincreasing, and right continuous. Golovach and Petrov proved that the Golovach function for a complete graph on more than five vertices may have nonunit jumps. The jumps of the Golovach function for the case of trees are considered. Examples of trees which disprove the conjecture that the Golovach function has only unit jumps for any planar graph are given and the Golovach function is constructed. It is shown that the Golovach function for trees with at most 27 edges has only unit jumps. The same assertion is proved for trees containing at most 28 edges all of whose vertices have degree at most 3. The examples mentioned above have minimum number of edges. For a graph with degenerate Golovach function, author analyses the problem of whether it is possible to eliminate nonunit jumps of the Golovach function by an arbitrarily small change of the edge lengths. Given are suitable small changes of edge lengths for the examples mentioned above.