scientific article; zbMATH DE number 1149743

MaRDI QIDQ4387119zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach, N. N. Petrov

Publication date 31 October 1999

zbMATH Keywords

evasionpursuitsearching on graphs

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Review text

The following kind of pursuit-evasion game on a finite connected graph \(\Gamma\) in \(\mathbb{R}^3\) is studied: There is a single evader with maximum speed \(\mu\), and \(n\) pursuers with maximum speed 1 who cannot ``see the evader but succeed in capturing it if one of them comes within a distance \(\varepsilon\) of it. The problem is to determine the minimum number \(S^{\varepsilon}_{\mu}(\Gamma)\) of pursuers for which the pursuers can be certain of capturing the evader. The graphs considered here are \(T, C\) and \(O\), the graphs consisting of all edges and vertices of a tetrahedron, cube and octahedron, respectively. With \(\Gamma=T, C\) or \(O\), the numbers \(S_{\infty}^{\varepsilon}(\Gamma)\) are found for all \(\varepsilon>0\), and \(S_{\mu}^0(\Gamma)\) for all \(\mu\geq 1\). Also it is shown that \(S_{\mu}^0(T)\leq 2\) for \(\mu\leq{1\over 3}\), \(S_{\mu}^0(C)\leq 3\) for \(\mu\leq 0.5\) and \(S_{\mu}^0(C)\leq 2\) for \(\mu\leq 0.2\). The paper concludes with some conjectures as open problems. For the entire collection see [Zbl 0879.00031].

Recommendations

• The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. II
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. I
• scientific article; zbMATH DE number 6706329
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. III
• scientific article; zbMATH DE number 4133868

Cited in

(8)

• The search for the evader on 3-minimal trees
• The pursuit-evasion game on the 1-skeleton graph of a regular polyhedron. II
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. I
• scientific article; zbMATH DE number 4133868 (Why is no real title available?)
• Search problems on graphs of regular polyhedra
• The pursuit-evasion game on the 1-skeleton graph of the regular polyhedron. III
• scientific article; zbMATH DE number 1102014 (Why is no real title available?)
• scientific article; zbMATH DE number 1164584 (Why is no real title available?)

This page was built for publication:

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