Arbitrarily large jumps of the Golovach function for trees

DOI10.3103/S106345411101002XMaRDI QIDQ1759500zbMATH OpenFDO

Authors Xianqiang Yang

Publication date 21 November 2012

Published in Vestnik St. Petersburg University. Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/S106345411101002X

zbMATH Keywords

\(\varepsilon\)-search problemGolovach functionlarge jumpspursuers and evadersearch numbers

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Search theory (90B40) Positional games (pursuit and evasion, etc.) (91A24)

Review text

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 for trees. As it is known, the Golovach function for trees with at most 27 edges has only unit jumps. In the authors' earlier papers, examples of trees on which the Golovach function has a jump of size 2 were constructed. In the present paper, it is shown that the jumps of the Golovach function for trees may be arbitrarily large. A sharp bound for the size of jumps is given for a sequence of trees constructed in the paper. A theorem about small perturbations of edge lengths for trees is proved, which asserts that an arbitrarily small perturbation of the edge lengths of a given tree (whose Golovach function may be degenerated) may yield a new tree whose Golovach function has only unit jumps.

Recommendations

• Nontrivial discontinuities of the Golovach functions for trees
• Integral trees of arbitrarily large diameters
• The Gorin-Shkolnikov identity and its random tree generalization
• The \(\ell_{p}\)-function on trees
• Asymptotic results on Hoppe trees and their variations
• A refinement of the formula for \(k\)-ary trees and the Gould-Vandermonde's convolution
• Specialising Aronszajn trees by countable approximations
• On Erdős-Sós conjecture for trees of large size
• Publication:4941038
• Entire functions arising from trees

Cited in

(6)

• Nontrivial discontinuities of the Golovach functions for trees
• On some problems of guaranteed search on graphs
• The theory of guaranteed search on graphs
• The realizability problem for Golovach-type functions
• Graph searching games with a radius of capture
• Monotonicity of the search number in the Golovach problem

This page was built for publication: Arbitrarily large jumps of the Golovach function for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759500)